연습 목표
빠른 존재 확인과 누적 상태가 필요한 문제 주문 할인이라는 업무 맥락을 빌려, 패턴을 암기하지 않고 제약 조건에서 선택 근거를 만드는 연습입니다.
1. 문제를 읽는 순서
입력 크기와 정답 조건을 먼저 표시하고, 작은 예시 세 개를 손으로 풉니다. 그 다음 정확한 브루트포스를 적어 병목을 찾습니다.
- 빈 입력·원소 하나·최댓값을 예시에 넣는다.
- 시간과 공간 복잡도의 상한을 입력 크기로 계산한다.
- 정답의 순서 보장과 중복 허용 여부를 확인한다.
2. 패턴 선택 근거
해시·빈도표은 빠른 존재 확인과 누적 상태가 필요한 문제에 적합합니다. 단, 자료가 정렬되어 있는지, 상태가 되돌아가는지, 한 번의 순회로 충분한지를 확인한 뒤 적용해야 합니다.
- 상태 변수의 의미를 한 문장으로 말한다.
- 반복마다 유지해야 하는 불변 조건을 적는다.
- 표준 라이브러리를 쓸 경우 연산 비용을 확인한다.
3. 면접형 설명과 검증
풀이를 설명할 때는 코드 줄 대신 상태, 갱신 규칙, 종료 조건, 복잡도 순서로 말합니다. 구현 뒤에는 예시를 다시 대입해 인덱스와 경계값을 검증합니다.
- 브루트포스와 개선된 풀이의 차이를 말한다.
- 오프바이원과 오버플로우 가능성을 점검한다.
- 테스트 케이스를 최소 네 개 추가한다.