[우선순위 큐] 백준 1655번: 가운데를 말해요 / 골드 2

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

import sys
import heapq
input = sys.stdin.readline

n = int(input())
max_heap = []
min_heap = []
for i in range(n):
    cur = int(input())
    if i == 0:
        heapq.heappush(max_heap, -cur)
        heapq.heappush(min_heap, cur)
        print(-max_heap[0])
        continue

    if i % 2 == 1:
        if min_heap[0] <= cur:
            heapq.heappush(min_heap, cur)

        else:
            heapq.heappush(max_heap, -cur)
            heapq.heappop(max_heap)

            heapq.heappush(min_heap, -max_heap[0])

    else:
        if min_heap[0] <= cur:
            heapq.heappush(min_heap, cur)
            heapq.heappop(min_heap)

            heapq.heappush(max_heap, -min_heap[0])
        else:
            heapq.heappush(max_heap, -cur)

    print(-max_heap[0])

처음엔 쉽게 느껴져도 시간 제한이 매우 빡세기 때문에 

일반적인 방법으로는 풀리지 않는다. 

 

우선순위큐 중 최대힙, 최소힙은 많이 사용도 해봤고 써먹어도 봤지만

이 문제는 한번도 안해본 이른바 중간힙(?)을 구현해야 한다.

 

아래 그림은 예제 출력이 나오는 원리를 직접 그려본 것인데, 여기서 힌트를 얻을 수 있다.

이를 구현하려면 최대힙, 최소힙 자료구조가 각각 하나씩 필요하다. (사실 이건 질문코너에서 힌트를 얻음)

중간 노드를 기준으로 2, 1, -99 이렇게 떨어지는 것을 최대 힙으로 구현하고

2, 5, 7, 10 으로 증가하는 것은 최소 힙으로 구현한다.