[Python] 백준 7662 : 이중 우선순위 큐

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

접근 방법

하나의 Priority Queue를 두 가지 기준으로 만들 수는 없으니, 결국 2개의 Priority Queue를 선언해야한다.

 

Priority Queue의 종류 중 heapq를 사용하여 구현하였다.

heapq는 기본적으로 min-heap으로 구성된다. 따라서, max-heap을 구성하기 위해서는 value에 음수를 취하여 넣고 pop할 때도 음수를 취하여 사용하면 된다.

 

이 문제의 핵심은 2개의 우선순위 큐를 동기화하는 것이다.

나는 해시 테이블 popHistory를 이용해 동기화를 처리하였다.

<key, value>에서 key는 n를 나타내고, value는 해당 n이 몇 개 존재하는지를 나타낸다.

pop할 때 value를 하나씩 감소한다면, 동기화할 때 0일 경우 해당 n은 무시하도록 처리한다.

코드에 동기화 하는 부분을 주석처리 하였으니 보면서 이해가 되었으면 한다.

 

코드

# TITLE: 이중 우선순위 수 (https://www.acmicpc.net/problem/7662)
# LEVEL: Gold 4
# TAG: data_structures, priority_queue
# DATE: 20221101
# AUTHOR: squareyun

import heapq
import sys
INF=1e9
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    minheap = []
    maxheap = []
    popHistory = dict()
    k = int(input())
    for _ in range(k):
        op, n = input().split()
        if op == 'I':
            n = int(n)
            heapq.heappush(minheap, n)
            heapq.heappush(maxheap, -n)
            if n in popHistory:
                    popHistory[n] += 1
            else:
                popHistory[n] = 1

        elif op == 'D':
            if n == '1':
                while len(maxheap) != 0:
                    popElement = -heapq.heappop(maxheap)
                    if popHistory[popElement] != 0: #동기화
                        popHistory[popElement] -= 1
                        break

            elif n == '-1':
                while len(minheap) != 0:
                    popElement = heapq.heappop(minheap)
                    if popHistory[popElement] != 0: #동기화
                        popHistory[popElement] -= 1
                        break
    #maxheap 동기화
    answerMax, answerMin = -INF, INF
    while len(maxheap) != 0:
        if popHistory[-maxheap[0]] != 0 :
            answerMax = -maxheap[0]
            break
        else:
            heapq.heappop(maxheap)

    #minheap 동기화
    while len(minheap) != 0:
        if popHistory[minheap[0]] != 0 :
            answerMin = minheap[0]
            break
        else:
            heapq.heappop(minheap)

    if answerMax == -INF or answerMin == INF:
        print('EMPTY')
    else:
        print(f'{answerMax} {answerMin}')