반례 드립니다. 반례도 반례이지만, 중간에 insert하는 것은 최대 O(n)이 걸리기 때문에 이 방법은 고쳐도 시간초과가 날 것 같습니다. https://www.acmicpc.net/blog/v... 의 python 부분을 확인해 보세요.

입력:

4
-3
7
6
5

출력:

-3
-3
6
-3

정답 출력:

-3
-3
6
5

24번째 줄을 고치고 제출했는데 예상대로 시간 초과가 떴습니다.

그런데 제가 깜빡하고 input을 stdin형식으로 바꾸는 것을 안해서 다시 고쳐서 제출했더니 468ms로 맞았습니다가 떴습니다

파이썬으로는 heapq으로만 풀 수 있게 시간이 설정되었을 것이라고 생각했는데 의외네요.

혹시 이거 재채점이 필요한 것일까요?

오 상당히 의외군요.. 시간 제한이 상당히 빡빡한데도 n^2이 통과했다는 것은 insert 저격 데이터 (항상 맨 처음에 insert하는 데이터) 가 없거나 pypy에서 insert에 대한 최적화를 해주는 거일수도 있겠네요. 문제 원래 의도를 지킬려면 저격 데이터를 추가하거나 n크기를 늘려야 할 것 같네요..