해당 문제에선 중간값을 계속해서 업데이트 하기 위해 힙을 두가지를 쓴다.
하나는 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])
우선순위힙을 두 개 이상 두어서 구현해본 건 처음인데, 이 문제 덕분에 힙을 활용하는 방식에 대해 하나 더 터득한 것 같다 굿 !