[우선순위 큐/Python] 1655번: 가운데를 말해요 - 효과는 굉장했다!

1655번: 가운데를 말해요

 

알고리즘 분류

• 자료 구조
• 우선순위 큐

 

 

SOLUTION

import sys
import heapq

N = int(sys.stdin.readline())
left = []
right = []

for _ in range(N):
    num = int(sys.stdin.readline())
    
    if len(left) == len(right):
        heapq.heappush(left, (-num, num)) # 최대 힙

    else:
        heapq.heappush(right, (num, num)) # 최소 힙
        
    # 왼쪽 루트가 오른쪽 루트보다 크다면 자리를 바꿔준다
    if right and left[0][1] > right[0][1]:
        rightValue = heapq.heappop(right)[1]
        leftValue = heapq.heappop(left)[1]
        # left에는 가장 큰 수가 root가 되어야 한다
        heapq.heappush(left, (-rightValue, rightValue))
        # right에는 가장 작은 수가 root가 되어야 한다
        heapq.heappush(right, (leftValue, leftValue))

    print(left[0][1])