[BOJ] 이중 우선순위 큐

---

코드

import sys
import heapq
input = sys.stdin.readline

# 파이썬 heapq는 min heap
def operation(op, num, i):
    if op == 'I':
        heapq.heappush(minheap, (num,i))
        heapq.heappush(maxheap, (-num,i))
        exist[i] = True
    if op == 'D':
        if num == 1:
            while maxheap and not exist[maxheap[0][1]]:
                heapq.heappop(maxheap)
            if maxheap:
                exist[maxheap[0][1]] = False
                heapq.heappop(maxheap)
        elif num == -1:
            while minheap and not exist[minheap[0][1]]:
                heapq.heappop(minheap)
            if minheap:
                exist[minheap[0][1]] = False
                heapq.heappop(minheap)

        while maxheap and not exist[maxheap[0][1]]:
                heapq.heappop(maxheap)
        while minheap and not exist[minheap[0][1]]:
                heapq.heappop(minheap)

T = int(input())

for _ in range(T):
    minheap = []
    maxheap = []
    K = int(input())
    exist = [False for _ in range(K)]
    for i in range(K):
        op, n = input().split()
        operation(op, int(n), i)

    if minheap and maxheap:
        print(-maxheap[0][0], minheap[0][0])
    else:
        print('EMPTY')

결과

풀이 방법

• 파이썬의 heapq 모듈을 사용하면 최소 힙(MIN-HEAP)의 기능을 사용할 수 있다.
• 최소값을 구하여 제거할 땐 최소힙을, 최대값을 구하여 제거할 땐 최대힙을 사용하기 위해 2개의 힙을 사용하였다.
• 다만 파이썬은 최소 힙만 제공하므로 최대 힙을 구현하려면 삽입할 땐 우선순위를 음수화하여 삽입하고, pop하여 사용할 땐 -를 제거하여 사용해야 한다.
• 삽입연산만 한다면 2개의 힙을 사용하는 것이 문제되지 않지만, 제거연산을 위해서는 A힙에서 제거한 노드가 B힙에서도 제거되어야 한다 (동기화).
• 이를 위해 삽입 시 데이터뿐만 아니라 해당 데이터가 k개의 주어진 연산 중 몇 번째(i) 연산에서 추가된 데이터인지를 저장하고, exist 리스트에 i번째 연산에 추가된 데이터가 존재하는지 여부를 True / False로 표시한다.
• 이렇게 하면 힙의 루트(min or max)를 제거하기 전에 해당 값이 이미 다른 힙에서 제거된 값인지 exist 리스트를 확인하여 False이면 pop처리함으로써 제거작업 전 동기화를 하게 된다.

---