[우선순위큐/파이썬] 백준 7662번 이중 우선순위 큐 / 골드 5

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

7662번: 이중 우선순위 큐

import heapq
test = int(input())
for _ in range(test):
    commands = int(input())
    popped = [False for _ in range(commands)]
    min_heap = []
    max_heap = []
    num = 0
    for c in range(commands):
        command, n = input().split()
        n = int(n)
        if command == 'I':
            heapq.heappush(min_heap, [n, c])
            heapq.heappush(max_heap, [-n, c])
            num += 1
        if command == 'D':
            if num == 0:
                continue
            if n == 1:  # delete max val
                _, idx = heapq.heappop(max_heap)
                while popped[idx]:
                    _, idx = heapq.heappop(max_heap)
                popped[idx] = True

            else:  # delete min val
                _, idx = heapq.heappop(min_heap)
                while popped[idx]:
                    _, idx = heapq.heappop(min_heap)
                popped[idx] = True
            num -= 1

    if num == 0:
        print("EMPTY")
        continue

    val, idx = heapq.heappop(min_heap)
    while popped[idx]:
        val, idx = heapq.heappop(min_heap)
    min_val = val

    val, idx = heapq.heappop(max_heap)
    while popped[idx]:
        val, idx = heapq.heappop(max_heap)
    max_val = -val

    print(max_val, min_val)

시간 제한을 넘지 않으면서 최대힙, 최소힙 기능을 모두 가지고 있는 이중 우선순위큐를 구현하는 문제다.

 

힙 하나를 이용하여 푸는 시도를 했으나, 실패했다.

최소힙 기능을 가지도록 구현을 하면, 최댓값을 뽑아낼 방법이 완탐말고는 생각나지 않았다. 

물론 완탐으로 하면 시간초과가 난다.

 

힙 두개를 만들어서 푸는 방법이 사실 쉽게 떠올릴 수 있는 방법인데

관건은 두 힙의 상태를 동기화시켜주는 것이다. 

일단 힙푸시를 할때는 숫자값과 함께 일종의 id 역할을 해주는 c값을 같이 집어넣어주었다. 

팝을 할때는 최대값을 빼야할 경우 최대힙에서 팝을, 최소값을 빼야할 경우 최소힙에서 팝을 해준다. 이때 동기화에 신경을 써야한다. 최대힙에서 뺀 최댓값이 빠졌다는 사실을 최소힙에서도 알아야하기 때문에

popped 리스트를 따로 만들어 pop여부를 저장하기로 했다. 접근은 id로 한다.