[백준] 가운데를 말해요

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

1655번: 가운데를 말해요

 

heapq 를 이용하여 bigger 과 smaller 인 queue 를 만들어서 기준이 되는 중간값(bigger[0]) 을 기준으로 크면 bigger, 작으면 smaller 에 추가해준다.

 

bigger[0] 은 값이 추가될 때, 그 값이 smaller 의 어떤 원소보다 작을 수 있으므로 smaller[0] 과 비교하여 작으면 교체해준다.

 

import sys, heapq

N = int(sys.stdin.readline())
bigger = []
smaller = []
answer = []

for i in range(N):
    heapq.heappush(bigger, int(sys.stdin.readline()))
    
    if len(bigger) - len(smaller) == 3:
        heapq.heappush(smaller, -heapq.heappop(bigger))
    else:
        if smaller:
            M, m = heapq.heappop(bigger), -heapq.heappop(smaller)
            heapq.heappush(bigger, max(M, m))
            heapq.heappush(smaller, -min(M, m))
    
    answer.append(bigger[0])

for i in answer:
    print(i)