BaekJoon1655_가운데를 말해요

문제

풀이

시간제한이 0.1초로 매우 짧아 자료구조를 적절히 활용해야 하는 문제이다. 단순하게 생각해서 중간값만 계속 계산해내면 되니 heapq를 2개 만들어 활용하면 된다.
즉, 계속해서 중간값보다 작은 값을 저장하는 큐 하나와 그 반대되는 경우의 큐 하나를 만들어 저장하면 작은값이 저장되는 큐의 루트가 중간값이 된다.

풀이 코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())

min_heap = []
max_heap = []

for _ in range(n):
    num = int(input())

    if len(min_heap) == len(max_heap):
        heapq.heappush(min_heap, -num)
    else:
        heapq.heappush(max_heap, num)

    print(min_heap, "min_h")
    print(max_heap, " max_h")
    if max_heap and max_heap[0] < -min_heap[0]:
        a = heapq.heappop(min_heap)
        b = heapq.heappop(max_heap)

        heapq.heappush(min_heap, -b)
        heapq.heappush(max_heap, -a)
    
    print(-min_heap[0])