프로그래머스 / 1655 / 가운데를 말해요 / python

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

n = int(input())

left = []
right = []
for _ in range(n):

    k = int(input())
    if left and -left[0] > k:
        heappush(left, -k)
        if len(left) > len(right) + 1:
            heappush(right, -heappop(left))
    else:
        heappush(right, k)
        if len(right) > len(left):
            heappush(left, -heappop(right))
    # print(left, right)
    print(-left[0])
    

heap 알고리즘을 사용하여 해결한 문제
왼쪽 힙은 최대힙, 오른쪽 힙은 최소힙으로 하고 크기 비교는 항상 왼쪽 heap을 기준으로 하면 가운데 값을 계속 출력할 수 있다.

크기는 같거나 왼쪽이 하나 더 커야하므로 힙에 넣었을 때 크기를 비교해 줘서 맞춰준다.