제가 사용한 방법은 다음과 같습니다.

0. I/O (43줄~56줄)

1. 우선 머지소트로 소팅한 후,

2. 이분 탐색으로 아무거나 하나를 찾습니다. (int find)  (58줄)

2-1. 못찾으면 그대로 0 출력  (59-62줄)

2.2. 기존의 히스토리에서 찾은 적이 있는 숫자일 경우 같은 알고리즘으로 같은 find를 구했을 것이니 바로 판별해 줍니다. (63-66줄)

3. 왼쪽으로 0부터 find-1까지 이분 탐색한 후 여전히 같으면 0부터 left-1까지 탐색한 후.... 반복 (71~75줄)

3-1. 오른쪽 동일 (76~80줄)

4. history 업데이트 (82줄)

이렇게 코드를 짜 보았습니다. 문제가 되는 부분은 아마 3번일텐데요, 게시글들을 읽어 보니 upper bound와 lower bound를 찾는 과정에서 linear search를 하게 되면 모든 숫자가 같은 최악의 경우에 linear search와 같아지는게 문제가 된다고 하였습니다.

그런데 제가 한 방법도 그런가요?

아니라고 생각한 이유는 다음과 같습니다.

1~500000가 모두 같은 숫자이면, 먼저 find는 250000이 나옵니다.

그 다음 왼쪽으로 찾으면 125000, 그 다음 67500, 이런식으로 가다가 1까지 log(250000)번만에 lower bound를 찾게 되고, 오른쪽도 동일합니다.

따라서  2log(n/2), 즉 결국 logn이라고 생각했습니다.

총합해보면 1번이 nlogn, 2번이 logn, 3번이 logn이라서 문제 될 게 없어보이는데..  1%도 안뜨고 시간초과가 나서 참 당황스럽습니다. 실제 테케로 50만개짜리 넣어봐도 금방 나오는 것 같아 보이는데 말이죠..

제가 생각하지 못한 다른 문제점이 있을 것 같습니다. 조언 부탁드립니다!!