[백준] 1655번 : 가운데를말해요

1655번: 가운데를 말해요

해당 문제는 2개의 우선순위 큐를 사용하여 문제를 해결 하였습니다.

Left큐 : 최대 우선순위 힙큐

Right큐 : 최소 우선순위 힙큐

Left[0] 이 중간값 항상 임을 보장합니다. → Light큐와 RIght큐에 번갈아 가면서 삽입했기 때문입니다.

Left[0] 의 뒷쪽 원소들의 값은 Left[0] 보다 작은수를 보장해야합니다.

Right[0 ~ End] 원소들은 Left[0] 값보다 큰수를을 보장해야합니다.

import heapq
import sys
leftq = []
rightq = []
N = int(input())

for _ in range(N):
    num = int(sys.stdin.readline())
    
    if len(leftq) != len(rightq):
        heapq.heappush(rightq, num)
    else:
        heapq.heappush(leftq, -num)
    
    if rightq and rightq[0] < -leftq[0]:
        rightnum = heapq.heappop(rightq)
        leftnum = heapq.heappop(leftq)
        heapq.heappush(rightq, -leftnum)
        heapq.heappush(leftq, -rightnum)
    
    print(-leftq[0])