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

문제 요약

이중 우선순위 큐는 정수를 저장하고, 최댓값 또는 최솟값을 삭제하는 연산을 지원한다.

주어진 연산 명령을 수행한 후 큐에 남아 있는 값 중 최댓값과 최솟값을 출력한다.

만약 큐가 비어 있다면 'EMPTY'를 출력한다.

 

풀이 설명

문제를 해결하기 위해 두 개의 우선순위 큐 (최소 힙과 최대 힙)를 사용한다.
또한 각 숫자의 등장 횟수를 저장하는 딕셔너리를 사용하여, 삭제 연산 시 실제로 큐에서 존재하는 숫자를 관리한다.

 

풀이 코드

from collections import deque
import heapq
import sys

input = sys.stdin.readline

def is_empty(nums):
    for item in nums:
        if item[1] > 0:
            return False
    return True

def dual_priority_queue(operations):
    min_heap = []
    max_heap = []
    nums = {}

    for operation in operations:
        op, num = operation.split()
        num = int(num)

        if op == 'I':
            if num in nums:
                nums[num] += 1
            else:
                nums[num] = 1
                heapq.heappush(min_heap, num)
                heapq.heappush(max_heap, -num)

        elif op == 'D':
            if not is_empty(nums.items()):
                if num == 1:
                    while -max_heap[0] not in nums or nums[-max_heap[0]] < 1:
                        temp = -heapq.heappop(max_heap)
                        if temp in nums:
                            del nums[temp]
                    nums[-max_heap[0]] -= 1
                elif num == -1:
                    while min_heap[0] not in nums or nums[min_heap[0]] < 1:
                        temp = heapq.heappop(min_heap)
                        if temp in nums:
                            del nums[temp]
                    nums[min_heap[0]] -= 1

    if is_empty(nums.items()):
        return "EMPTY"
    else:
        while min_heap[0] not in nums or nums[min_heap[0]] < 1:
            heapq.heappop(min_heap)
        while -max_heap[0] not in nums or nums[-max_heap[0]] < 1:
            heapq.heappop(max_heap)
        return f"{-max_heap[0]} {min_heap[0]}"

T = int(input().strip())
results = []

for _ in range(T):
    k = int(input().strip())
    operations = [input().strip() for _ in range(k)]
    results.append(dual_priority_queue(operations))

for result in results:
    print(result)

 

설명

1. 큐 초기화:
   • 두 개의 우선순위 큐(min_heap과 max_heap)를 사용하여 최소값과 최대값을 각각 관리
   • 숫자의 등장 횟수를 저장하는 딕셔너리 nums를 사용
2. 연산 처리:
   • I n 연산은 숫자 n을 큐에 삽입. min_heap과 max_heap에 각각 삽입하고, nums 딕셔너리에 등장 횟수를 기록.
   • D 1 연산은 최댓값을 삭제. max_heap에서 최댓값을 꺼내고, nums 딕셔너리에서 등장 횟수를 감소시킴
   • D -1 연산은 최솟값을 삭제. min_heap에서 최솟값을 꺼내고, nums 딕셔너리에서 등장 횟수를 감소시킴
3. 최종 결과 처리:
   • 연산을 모두 처리한 후, 큐가 비어 있는지 확인
   • 비어 있으면 "EMPTY"를 반환하고, 그렇지 않으면 min_heap에서 최솟값을, max_heap에서 최댓값을 꺼내어 출력