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

15 Jan 2023 in Study on Algorithm

백준7662 이중 우선순위 큐 링크

문제

예제 입력

---

코드

import sys
import heapq
t = int(input())

for _ in range(t):
    k = int(input())
    max_heap = []
    min_heap = [] # heapify(리스트)
    visited = [False] * k

    for key in range(k):
        Q, N = sys.stdin.readline().split()
        if Q == 'I':
            heapq.heappush(min_heap, (int(N), key))
            heapq.heappush(max_heap, (-int(N), key))  # (우선 순위, 값)
            visited[key] = True
        if Q == 'D':
            if N == '1' and max_heap:
                visited[max_heap[0][1]] = False
                heapq.heappop(max_heap)
            if N == '-1' and 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 not max_heap or not min_heap:
        print('EMPTY')
    else:
        print(-max_heap[0][0], min_heap[0][0])

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 list를 사용하여 이중 우선순위 큐를 구현했습니다.

가장 효율적인 우선순위 큐의 구현 방법은 트리 구조를 사용하는 힙이고 파이썬에서의 우선순위 큐는 heapq모듈을 사용합니다. 
heapq 모듈에는 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줍니다.

---

결과