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

문제 링크

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

7662번: 이중 우선순위 큐

---

 

코드

import heapq
input = __import__('sys').stdin.readline
for _ in range(int(input())):
    n = int(input())
    visited = [False for _ in range(n)]
    max_heap, min_heap = [],[]
    for i in range(n):
        command = input()
        if command.startswith('I'):
            heapq.heappush(max_heap,(-int(command.split()[1]),i))
            heapq.heappush(min_heap,(int(command.split()[1]),i))
            visited[i] = True
        else:
            if command.split()[1]=='1':
                while max_heap and not visited[max_heap[0][1]]:
                    heapq.heappop(max_heap)
                if max_heap:
                    visited[max_heap[0][1]] = False
                    heapq.heappop(max_heap)
            else:
                while min_heap and not visited[min_heap[0][1]]:
                    heapq.heappop(min_heap)
                if min_heap:
                    visited[min_heap[0][1]] = False
                    heapq.heappop(min_heap)
    while min_heap and not visited[min_heap[0][1]]:heapq.heappop(min_heap)
    while max_heap and not visited[max_heap[0][1]]:heapq.heappop(max_heap)
    if max_heap and min_heap:print(-max_heap[0][0],min_heap[0][0])
    else:print("EMPTY")

---

문제 풀이

이중 우선순위 큐는 우선순위가 가장 높은 것과 우선순위가 가장 낮은 것을 삭제하는 연산이 필요하기 때문에 최대힙,최소힙 모두 필요하다.

삽입은 우선순위 큐와 동일하게 삽입하면 되고, 삭제는 'D 1', 'D -1'에 따라 최소힙을 최대힙으로, 최대힙을 최소힙으로 바꿔가며 삭제를 진행하는 것은 너무 비효율적이기에 최대힙과 최소힙의 상태를 동기화해주는 작업이 필요하다.

visited 배열을 하나 선언해서 최대힙과 최소힙의 상태를 공유하여 동기화를 진행할 수 있다. visited 가 True이면 이중 우선순위 큐에 존재하고 False이면 존재하지 않는다고 생각하면 된다.

삽입 연산은 최대힙,최소힙에 모두 삽입하며 visited를 True로 만든다.

최대힙을 기준으로 삭제 연산 진행을 보면, 최대힙에 존재하지만 visited 가 False인 것은 모두 pop한다. 그리고 visited가 True인, 최대힙에서 최대값을 pop하고 최소힙과 동기화를 위해 visited를 False로 만들어준다.

마지막으로, 최대힙과 최소힙에 visited가 False인 값이 남아있을 수 있으므로 모두 pop해준다.