[백준 1655] 가운데를 말해요 (Python) / G2

문제

1655. 가운데를 말해요

코드

# 1655. 가운데를 말해요
import heapq
import sys
input = sys.stdin.readline

n = int(input())
# 최대 힙
left = []
# 최소 힙
right = []

for i in range(1, n+1):
    now = int(input())

    if len(left) == len(right):
        heapq.heappush(left, -now)
    else:
        heapq.heappush(right, now)

    if right and (-1 * left[0]) > right[0]:
        l = heapq.heappop(left)
        r = heapq.heappop(right)

        heapq.heappush(right, -l)
        heapq.heappush(left, -r)
    print(left[0] * -1)

코드 설명

처음에 제한시간을 보고, 입력이 들어올 때마다 가운데 값을 꺼내야하는 것을 보고 우선순위 큐를 써야겠다 생각이 들었다.

중간값을 기준으로 왼쪽과 오른쪽 리스트를 나누고 왼쪽은 최대 힙, 오른쪽은 최소힙을 이용해 구현해주었다.

두 리스트의 길이가 같으면 왼쪽 넣어주고, 그게 아니라면 오른쪽에 넣어주고 난 후,
만약 왼쪽에서 가장 큰 값이 오른쪽 가장 작은 값보다 크다면 두 값을 바꿔서 리스트에 넣어주었다.
이렇게 하면 왼쪽 리스트의 가장 큰값이 항상 중간값이 되게 된다.