💻 백준 7662: 이중 우선순위 큐

문제 소개 🧐

이중 우선순위 큐는 데이터를 삽입, 삭제할 수 있는 자료 구조입니다. 일반적인 우선순위 큐와 달리, 삭제 연산 시 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 선택하여 삭제할 수 있습니다.

주어진 연산들을 처리한 후, 큐에 최종적으로 남아있는 최댓값과 최솟값을 출력하는 문제입니다.

입력 📝

  • 첫째 줄: 테스트 데이터의 수 T
  • 각 테스트 데이터의 첫째 줄: 연산의 개수 k (k ≤ 1,000,000)
  • 이후 k개의 줄: 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n
    • I n: 정수 n을 큐에 삽입
    • D 1: 큐에서 최댓값을 삭제
    • D -1: 큐에서 최솟값을 삭제

출력 📤

  • 모든 연산 처리 후 큐에 남은 최댓값과 최솟값을 공백으로 구분하여 출력
  • 큐가 비어있으면 “EMPTY”를 출력

제한 ❌

  • 시간: 6초
  • 메모리: 256MB
  • 정수 범위: -2^31 이상 2^31 미만

첫 번째 시도: PriorityQueue 사용 👊

Idea

PriorityQueue는 기본적으로 최소 힙(min-heap)으로 동작하므로 get() 메서드는 항상 최솟값을 반환한다. 최댓값을 삭제하기 위해 end 인덱스만 따로 관리하여 처리해보면 어떨까 생각했다.

Code

import sys
from collections import deque
from queue import PriorityQueue

t = int(sys.stdin.readline().rstrip())  # 입력 데이터의 수

while t:
# I 는 insert, D 1은 최댓값 pop, D -1은 최솟값 pop
    k = int(sys.stdin.readline().rstrip())  # 연산의 수
    Q = PriorityQueue()
    end = 0

    for _ in range(k):
        a, b = sys.stdin.readline().split()
        b = int(b)

        if a == 'I':
            Q.put(b)
            end += 1

        if a == 'D':
            if not end:  # 끝 인덱스가 0일때
                continue
            else:
                if b == -1:
                    Q.get()
                    end -= 1
                else:
                    end -= 1
    t-=1
    if end:
        min_Q = Q.get()
        max_Q = min_Q
        for i in range(end):
            max_Q = Q.get()
        print(max_Q, min_Q)
    else:
        print('EMPTY')

Result

  • 틀렸습니다
  • PriorityQueue에서 임의의 (최대) 원소를 제거하는 로직이 잘못되었다. get()은 항상 최솟값만 제거하므로, 최댓값을 직접 제거할 수 없습니다.

두 번째 시도: List와 인덱스 카운팅 ✨

Idea

list에 모든 원소를 저장하고, 최솟값/최댓값 삭제 연산이 들어올 때마다 실제로 pop하지 않고 카운트만 한다. 모든 연산이 끝난 후 리스트를 정렬하고, 카운트된 인덱스를 이용해 최종 최솟값과 최댓값을 구하는 방식으로 진행해보려 했다.

Code

import sys
from collections import deque
from queue import PriorityQueue

t = int(sys.stdin.readline().rstrip())  # 입력 데이터의 수

while t:
# I 는 insert, D 1은 최댓값 pop, D -1은 최솟값 pop
    k = int(sys.stdin.readline().rstrip())  # 연산의 수
    Q = list()
    min_pop, max_pop = 0, 0
    length = 0

    for _ in range(k):
        a, b = sys.stdin.readline().split()
        b = int(b)

        if a == 'I':
            Q.append(b)
            length += 1

        if a == 'D':
            if not length:
                continue
            if b == -1:
                min_pop += 1
            else:
                max_pop -= 1
            
            length -= 1
    t-=1
    if length > 0:
        Q.sort()
        print(Q[-1 + max_pop], Q[min_pop])
    else:
        print('EMPTY')

Result

  • 실패
  • 중간에 어떤 값이 삭제되었는지 추적할 수 없기 때문에, 마지막에 정렬하더라도 이미 삭제된 값이 최솟값/최댓값으로 잘못 선택될 수 있다는 것을 뒤늦게 알아챘다.

세 번째 시도: 최소 힙과 최대 힙 동기화 ✅

Idea

최소 힙과 최대 힙, 두 개의 우선순위 큐를 동시에 사용합니다.

  1. 삽입: 원소를 최소 힙에 그대로, 최대 힙에는 부호를 바꿔서 삽입합니다.
  2. 삭제:
    • 최솟값 삭제: 최소 힙에서 원소를 pop합니다.
    • 최댓값 삭제: 최대 힙에서 원소를 pop합니다.
  3. 동기화: 한쪽 힙에서 삭제된 원소가 다른 쪽 힙에는 여전히 남아있을 수 있습니다 (이를 ‘유령 데이터’라 칭함). 이를 해결하기 위해, 각 숫자의 개수를 dict에 저장합니다. pop을 수행할 때, 해당 원소의 개수가 0이라면 이미 다른 힙에서 삭제된 것이므로, 유효한 원소가 나올 때까지 계속 pop하여 유령 데이터를 제거합니다.

Code

import sys
import heapq

t = int(sys.stdin.readline())

for _ in range(t):
    k = int(sys.stdin.readline())
    min_heap, max_heap = [], []
    counts = dict()

    for _ in range(k):
        op, n_str = sys.stdin.readline().split()
        n = int(n_str)

        if op == 'I':
            heapq.heappush(min_heap, n)
            heapq.heappush(max_heap, -n)
            counts[n] = counts.get(n, 0) + 1
        
        elif n == 1: # 최댓값 삭제
            # 먼저 유령 데이터들을 모두 제거
            while max_heap and counts.get(-max_heap[0], 0) == 0:
                heapq.heappop(max_heap)
            
            if max_heap:
                removed = -heapq.heappop(max_heap)
                counts[removed] -= 1
        
        else: # 최솟값 삭제
            # 먼저 유령 데이터들을 모두 제거
            while min_heap and counts.get(min_heap[0], 0) == 0:
                heapq.heappop(min_heap)
            if min_heap:
                removed = heapq.heappop(min_heap)
                counts[removed] -= 1
                
    # 모든 연산 후, 최종적으로 힙에 남은 유령 데이터들을 정리
    while max_heap and counts.get(-max_heap[0], 0) == 0:
        heapq.heappop(max_heap)
    while min_heap and counts.get(min_heap[0], 0) == 0:
        heapq.heappop(min_heap)
        
    if not max_heap or not min_heap:
        print("EMPTY")
    else:
        print(-max_heap[0], min_heap[0])

Result

  • 성공
  • 두 개의 힙과 dict를 이용해 상태를 동기화하는 전략이 통했다. 허상 데이터를 처리하는 과정이 핵심이었다.

개선할 부분 🤔

  • 각 힙의 상태를 동기화하는 로직을 함수로 분리하여 가독성을 높일 수 있을 것 같다.