BOJ 1655번: 가운데를 말해요

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

우선순위 큐를 이용하는 건데..

내가 파이썬의 heapq 라이브러리를 착각했다. 우선순위 큐는 정렬이 된 상태랑은 다른 건데 자동으로 정렬이 된다고 생각해서 1차로 틀렸고 그 이후에는 다른 풀이들을 보며 힌트를 좀 참고했다.

https://regularmember.tistory.com/142

이 블로그의 설명이 제일 이해하기 쉬웠는데, 이해하고 나니 알겠더라는,,,

근데!!!

파이썬으로 구현했는데 계속 시간초과가 나는 것이다.. 정말 머리 쥐어뜯으려는 찰나 질문 칸에 어떤 분의 파이썬 코드가 있어서 그걸 보았고, 유일하게 내 코드랑 다른 점이 입력받는 부분이라 설마..? 하고 입력받는 부분을 바꿔보았더니 통과가 됐다...

sys.stdin.readline().replace("\n", "")

이 코드 였는데.. 나는 지금껏 sys 를 사용하면 제일 빠른 줄 알았더니,, 그게 아닌가보다... 이건 또 처음보는 방식인데.. 다음에 파이썬에서 또 시간초과가 난다면 한 번 사용해봐야겠다...

import sys, heapq
N = int(sys.stdin.readline().replace("\n", ""))
maxh = []
minh = []
cnt = 0
for _ in range(N):
    n = int(sys.stdin.readline().replace("\n", ""))
    if (len(maxh)==len(minh)):
        heapq.heappush(maxh, [-n, n])
    else:
        heapq.heappush(minh, [n, n])
        
    if (minh and maxh[0][1] > minh[0][1]):
        a = heapq.heappop(maxh)[1]
        b = heapq.heappop(minh)[1]
        heapq.heappush(maxh, [-b, b])
        heapq.heappush(minh, [a,a])
    print(maxh[0][1])