백준 1655번 가운데를 말해요 | python | 우선순위힙

문제

링크

풀이

해당 문제에선 중간값을 계속해서 업데이트 하기 위해 힙을 두가지를 쓴다.
하나는 leftHeap(최대힙), 다른 하나는 rightHeap(최소힙)이다.

두 힙의 길이의 균형을 맞추기 위해 번갈아가며 현재값을 넣어주는 것이 핵심이다. 이렇게 하면 중간값은 항상 LeftHeap의 첫번째 원소라고 간주할 수 있다.

대신 현재 값을 넣고 나서, leftHeap의 첫번째 원소보다 rightHeap의 첫번째 원소가 더 작을 땐 값을 swap 해준다.

leftHeap은 최소힙이므로 pop하거나 push할 때 꼭 음수부호 붙이는 것을 잊으면 안된다!

import heapq
import sys
input = sys.stdin.readline

n=int(input())
leftHeap=[]
rightHeap=[]
for _ in range(n):
    tar=int(input())
    if len(leftHeap)==len(rightHeap):
        heapq.heappush(leftHeap,-tar) # 최대힙으로 구성
    else:
        heapq.heappush(rightHeap,tar)

    if rightHeap and rightHeap[0] < -leftHeap[0]:
        leftvalue=heapq.heappop(leftHeap)
        rightvalue=heapq.heappop(rightHeap)
        heapq.heappush(rightHeap,-leftvalue)
        heapq.heappush(leftHeap,-rightvalue) # 최대힙 넣어줄 때 -(음수부호) 붙일 것 !!
    print(-leftHeap[0])

우선순위힙을 두 개 이상 두어서 구현해본 건 처음인데, 이 문제 덕분에 힙을 활용하는 방식에 대해 하나 더 터득한 것 같다 굿 !