친구 이름 찾기

빠진 학생의 이름을 $x$라고 하자.

$n>1$이면 6반에서 $x$의 바로 앞 학생은 $a_{n-1}$이어야 하므로 $a_{n-1}<x$여야 한다. $n<m$이면 $x$의 바로 뒤 학생은 $a_n$이어야 하므로 $x<a_n$이어야 한다.

따라서 각 이름 $x$에 대해 다음 두 조건만 검사하면 된다.

• $n>1$이면 $a_{n-1}<x$.
• $n<m$이면 $x<a_n$.

2학년 전체 명단은 이미 가나다순으로 정렬되어 있다. 조건을 만족하는 이름을 입력 순서대로 모으면 정답도 자동으로 가나다순이 된다.

각 테스트 케이스의 시간 복잡도는 $O(m+k)$이고, 후보를 저장할 때 공간 복잡도는 $O(k)$이다.

Solution written by GPT5.6