[programmers/python] 이중 우선순위 큐 – heapq와 lazy deletion으로 풀기

- url : https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스의 이중 우선순위 큐 문제는 "최댓값과 최솟값을 동시에 삭제하고 추적할 수 있는 큐"를 구현하는 문제다.
기본적인 우선순위 큐를 넘어서 두 방향의 삭제가 모두 가능한 구조이기 때문에,
단순한 heap 하나로는 구현할 수 없으며, 두 개의 힙을 사용한 동기화 처리가 필요하다.

---

문제 요약

• 다음과 같은 연산이 주어진다:
  • "I num": 정수 num을 큐에 삽입
  • "D 1": 현재 큐에서 최댓값 삭제
  • "D -1": 현재 큐에서 최솟값 삭제
• 모든 연산을 처리한 뒤:
  • 큐가 비어 있다면 [0, 0] 반환
  • 아니라면 [최댓값, 최솟값]을 반환

---

핵심 아이디어

1. 두 개의 힙 사용

• 최소값 추출을 위한 min-heap (queue_s)
• 최댓값 추출을 위한 max-heap (queue_b) (heapq는 min-heap이므로 -num으로 넣음)

2. lazy deletion (지연 삭제)

• heapq는 중간 요소를 삭제하는 기능이 없고, 삭제된 값도 heap 내부에 남아있기 때문에
• deleted[i] 배열로 "이미 삭제된 인덱스"를 표시하여
  삭제된 값은 이후 연산에서 건너뛰도록 처리

3. 삽입 시 고유 인덱스 부여

• 각 값에는 연산의 순서(i)를 인덱스로 함께 저장
• 이 인덱스를 기준으로 두 힙 간의 요소를 구분하고 삭제 여부도 추적

---

구현 코드

import heapq

def solution(operations):
    queue_b = []
    queue_s = []
    deleted = [0]*len(operations)

    for i, op in enumerate(operations): 
        cm, d = op.split()
        num = int(d)

        if cm == "I": 
            heapq.heappush(queue_b, (-num, -i))  # max heap
            heapq.heappush(queue_s, (num, i))   # min heap

        elif cm == "D" and num == 1:
            while queue_b:
                deleted_n, j = heapq.heappop(queue_b)
                if deleted[abs(j)] != 1: 
                    deleted[abs(j)] = 1
                    break

        elif cm == "D" and num == -1:
            while queue_s:
                deleted_n, j = heapq.heappop(queue_s)
                if deleted[j] != 1: 
                    deleted[j] = 1
                    break

    max_v = None
    while queue_b:
        val, j = heapq.heappop(queue_b)
        if deleted[abs(j)] == 0:
            max_v = -val
            break

    min_v = None
    while queue_s:
        val, j = heapq.heappop(queue_s)
        if deleted[j] == 0:
            min_v = val
            break

    if max_v is None or min_v is None:
        return [0, 0]
    else:
        return [max_v, min_v]

---

예제 테스트

print(solution(["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]))  
# → [0, 0]

print(solution(["I 5", "I 7", "D 1"]))  
# → [5, 5]

print(solution(["I 1", "I 2", "I 3", "D -1"]))  
# → [3, 2]

• heapq는 중간 삭제가 불가능하기 때문에 lazy deletion 기법이 필수
• 두 힙이 항상 완전히 동기화되어 있지 않음에 유의해야 함
• 마지막 결과 계산 시에는 각 힙에서 직접 유효값을 찾아야 정확함