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