[백준 1655] 가운데를 말해요 (python)

1655번: 가운데를 말해요

---

두개의 heap을 이용하자!

작은 수들은 maxheap에 큰 수들은 minheap에 저장하여 중앙값을 찾는다.

 

1. bigheap에 첫번째 수를 저장한다. (중앙값은 bigheap[0])
2. 두번째 수부터 중앙값(bigheap[0])보다 작다면 smallheap에 크다면 bigheap에 넣어준다.
3. bigheap의 길이가 (i//2)+1개를 유지할 수 있도록 두 힙길이를 조절해준다.

 

import sys
import heapq
input = sys.stdin.readline

N = int(input())
smallheap = []
bigheap = [int(input())]
print(bigheap[0])

for i in range(2, N+1):
    _input = int(input())
    if bigheap[0] > _input:
        heapq.heappush(smallheap, -_input)
    else:
        heapq.heappush(bigheap, _input)

    while len(bigheap) < (i//2)+1:
        heapq.heappush(bigheap, -heapq.heappop(smallheap))
    while len(smallheap) < i-((i//2)+1):
        heapq.heappush(smallheap, -heapq.heappop(bigheap))
        
    print(bigheap[0])