[백준/G2] 가운데를 말해요

 

이번주 예정된 마지막 알고리즘 문제이다. 백트래킹하다가 자료구조 보니까 살 맛난다..

힙을 두개 사용하는 것이 주요 아이디어이며,

 

중간값을 뽑아내야하기에 항상 minHeap(최소의 최대)크기가 maxHeap(최대의 최소)크기보다 크거나 같아야 한다.

그래야 -minHeap[0]을 가리킬때 그 위치가 한가운데, 짝수개의 원소라도 작은 수를 가리키게 된다.

import sys,math
input= sys.stdin.readline
import heapq as hq

N=int(input())

minHeap=[]
maxHeap=[]

li=[]

for _ in range(N):
    li.append(int(input()))

for i in range(N):

    if not minHeap:
        hq.heappush(minHeap, -li[i])

    else:
        # 중간값을 뽑아내야하므로, minHeap의 크기를 maxHeap크기 이상으로 맞춰야 함
        if len(minHeap) == len(maxHeap)+1:
            if li[i] >= -minHeap[0]:
                hq.heappush(maxHeap,li[i])
            else:
                hq.heappush(maxHeap, - (hq.heappop(minHeap)))
                hq.heappush(minHeap,-li[i])
        
        else:
            # 이번엔 maxHeap의 최소와 비교
            if li[i] > maxHeap[0]:
                hq.heappush(minHeap, - (hq.heappop(maxHeap)))
                hq.heappush(maxHeap, li[i])
            else:
                hq.heappush(minHeap, -li[i])

    print(-minHeap[0])