백준 알고리즘 1655번 가운데를 말해요(python)

우선순위 큐를 사용해서 빠르게 중앙값을 찾아야 되는 문제이다.

우선순위 큐를 2개(최대 힙, 최소 힙) 사용한다는 점이 핵심이다. 왼쪽 우선순위 큐는 최대 힙으로 최댓값이 맨 처음에

오도록 구현하고, 오른쪽 우선순위 큐는 최소 힙으로 최솟값이 맨 처음에 오도록 구현한다.

왼쪽과 오른쪽 우선순위 큐의 크기가 똑같다면 왼쪽 우선순위 큐에 값을 저장하고, 왼쪽 우선순위 큐의 첫 번째 값이

오른쪽 우선순위 큐의 첫 번째 값보다 큰 경우가 생기면 왼쪽 값을 오른쪽 값으로 바꿔주면 된다.

마지막에는 왼쪽 우선순위 큐의 맨 처음 값(최대 힙의 최댓값)을 출력해주면 된다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
leftq, rightq = [], []
for _ in range(N):
    n = int(input())
    if len(leftq) == len(rightq):
        heapq.heappush(leftq, (-n, n))
    else:
        heapq.heappush(rightq, (n, n))
    if rightq and leftq[0][1] > rightq[0][1]:
        left, right = heapq.heappop(leftq)[1], heapq.heappop(rightq)[1]
        heapq.heappush(leftq, (-right, right))
        heapq.heappush(rightq, (left, left))
    print(leftq[0][1])