Python - [백준 7662] 이중 우선순위 큐 (feat. 힙, 우선순위큐, Lazy Deletion)

 

참고 포스트:

 

2025.02.24 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 힙(Heap)으로 우선순위 큐 구현하기 (feat. Lazy Deletion)

 

 

 

 

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

 

BOJ_7662_이중 우선순위 큐 (Python)

 

이중 우선순위 큐는 최댓값과 최솟값을 모두 지원하는 우선순위 큐입니다.
일반적인 우선순위 큐는 최대 힙(Max Heap) 또는 최소 힙(Min Heap) 중 하나만 제공하지만,
이 문제에서는 두 가지 연산을 모두 수행할 수 있는 큐를 구현해야 합니다.

---

1. 문제 조건

📌 입력

• 첫 번째 줄에 테스트 케이스 개수 T가 주어집니다. (1 ≤ T ≤ 100)
• 각 테스트 케이스의 첫 번째 줄에는 연산 개수 K가 주어집니다. (1 ≤ K ≤ 1,000,000)
• 다음 K개의 줄에는 I n 또는 D x 형태의 연산이 주어집니다.
  • I n: 정수 n을 큐에 삽입합니다. (-2^31 ≤ n ≤ 2^31 - 1)
  • D 1: 큐에서 최댓값을 삭제합니다.
  • D -1: 큐에서 최솟값을 삭제합니다.

• 모든 연산 수행 후, 최댓값과 최솟값을 출력
• 큐가 비어 있으면 "EMPTY" 출력

📌 출력

• 모든 연산을 수행한 후, 큐에 남아 있는 최댓값과 최솟값을 출력합니다.
• 큐가 비어 있으면 "EMPTY"를 출력합니다.

🔹 제한 사항

• 1 ≤ T ≤ 100
• 1 ≤ K ≤ 1,000,000
• 입력값의 범위: -2^31 ≤ n ≤ 2^31 - 1
• 최악의 경우 1,000,000번의 연산을 효율적으로 수행해야 함 → O(K log K) 이내의 풀이 필요

 

---

2. Checkpoint

 

✅ 1. 두 개의 힙(Heap) 활용

• 최소 힙 (min_heap) → 최솟값을 빠르게 찾기 위해 사용
• 최대 힙 (max_heap) → 최댓값을 빠르게 찾기 위해 사용 (Python의 heapq는 최소 힙만 지원하므로, 값을 음수로 변환하여 최대 힙처럼 사용)

즉, 같은 숫자를 두 개의 힙에 저장하여 필요할 때 최댓값 또는 최솟값을 빠르게 가져올 수 있도록 관리

---

✅ 2. Lazy Deletion(지연 삭제) 기법 적용

힙을 이용하여 삭제 연산을 수행할 때, Heap 특성상 중간 요소를 바로 삭제할 수 없기 때문에
삭제할 값이 필요할 때까지 보류하는 Lazy Deletion 기법을 적용합니다.

• valid 딕셔너리를 이용하여 각 숫자가 유효한지(삭제되지 않았는지) 기록
  • 예: {10: 2, 5: 1} → 숫자 10은 2개, 숫자 5는 1개 존재
• 삭제 연산(D 1 또는 D -1)이 들어오면, 해당 힙에서 유효한 값이 나올 때까지 반복하여 제거

즉, valid를 사용하여 불필요한 값 삭제를 최소화하고, 힙의 구조를 유지하면서 빠르게 최댓값과 최솟값을 찾을 수 있도록 구현

 

        elif cmd == "D":
            if num == 1:  # 최대값 삭제
                while max_heap:
                    max_val = -heapq.heappop(max_heap)
                    if valid.get(max_val, 0) > 0:
                        valid[max_val] -= 1
                        break

            elif num == -1:  # 최소값 삭제
                while min_heap:
                    min_val = heapq.heappop(min_heap)
                    if valid.get(min_val, 0) > 0:
                        valid[min_val] -= 1
                        break

 

D가 1일 경우 최대값 삭제, D가 -1일 경우 최소값 삭제를 수행합니다.
이때 삭제하려는 값이 valid 딕셔너리의 KEY로 작용하며,
해당 KEY의 VALUE가 그 값이 현재 큐에 존재하는 개수가 됩니다.

즉,

• valid[max_val] > 0 → 현재 최대 힙에 남아있는 유효한 값
• valid[min_val] > 0 → 현재 최소 힙에 남아있는 유효한 값
• valid[max_val] == 0 또는 valid[min_val] == 0이면 이미 삭제된 값으로 간주됩니다.

그렇기 때문에 valid[max_val] == 0 또는 valid[min_val] == 0 상태에서 D 1 또는 D -1 을 실행한다면

더이상 -1 을 하지 않고 0 인상태를 유지하게 되고요.

 

    while max_heap and valid.get(-max_heap[0], 0) == 0:
        heapq.heappop(max_heap)

    while min_heap and valid.get(min_heap[0], 0) == 0:
        heapq.heappop(min_heap)

 

 

이후 max_heap과 min_heap의 값이 valid 딕셔너리 키로 작용하여, 밸류가 0 인지 아닌지 검사합니다.

밸류가 0일 경우 해당 값이 이미 삭제 된 값으로 간주 되기 때문에 heap.heapop(max_heap) 과 heap.heapop(min_heap)을 통해 해 heap에서 탈락하게 됩니다.

 

해당 과정이 Lazy Deletion(지연 삭제) 라고 할 수 있습니다.

 

---

3. 코드 구현 (Python)

import sys
import heapq

input = sys.stdin.readline

T = int(input().strip())  # 테스트 케이스 개수

for _ in range(T):
    K = int(input().strip())  # 연산 개수
    
    max_heap = []  # 최대 힙 (음수로 저장)
    min_heap = []  # 최소 힙
    valid = {}  # 삭제된 값 체크용 딕셔너리

    for _ in range(K):
        cmd, num = input().strip().split()
        num = int(num)

        if cmd == "I":  # 삽입 연산
            heapq.heappush(max_heap, -num)  # 최대 힙 (음수 저장)
            heapq.heappush(min_heap, num)   # 최소 힙 (그대로 저장)
            valid[num] = valid.get(num, 0) + 1  # 값 추가 (유효성 체크)

        elif cmd == "D":
            if num == 1:  # 최대값 삭제
                while max_heap:
                    max_val = -heapq.heappop(max_heap)
                    if valid.get(max_val, 0) > 0:
                        valid[max_val] -= 1
                        break

            elif num == -1:  # 최소값 삭제
                while min_heap:
                    min_val = heapq.heappop(min_heap)
                    if valid.get(min_val, 0) > 0:
                        valid[min_val] -= 1
                        break

    while max_heap and valid.get(-max_heap[0], 0) == 0:
        heapq.heappop(max_heap)

    while min_heap and valid.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])  # 최대값, 최소값 출력

---

import sys
import heapq

input = sys.stdin.readline

• sys.stdin.readline() : 입력 속도를 빠르게 하기 위해 사용합니다.
• heapq 모듈 : 최소 힙(Min Heap)을 구현하는 Python 표준 라이브러리입니다.

T = int(input().strip())  # 테스트 케이스 개수

• T : 테스트 케이스 개수를 입력받습니다.

 

3.1. 데이터 구조 초기화

for _ in range(T):
    K = int(input().strip())  # 연산 개수
    
    max_heap = []  # 최대 힙 (음수로 저장하여 사용)
    min_heap = []  # 최소 힙
    valid = {}  # 각 숫자의 유효성을 체크하는 딕셔너리

• max_heap : Python의 heapq는 최소 힙만 지원하므로, 최대 힙을 구현하기 위해 음수값을 저장합니다.
• min_heap : 최소 힙은 기본 heapq 사용합니다.
• valid : 숫자의 유효 여부를 저장하는 딕셔너리입니다. (삭제 여부 확인용)

---

3.2. 연산 처리

for _ in range(K):
    cmd, num = input().strip().split()
    num = int(num)

• cmd : 연산의 종류 (I 또는 D)
• num : 연산의 대상 숫자

3.2.1. 삽입 연산 (I n)

if cmd == "I":
    heapq.heappush(max_heap, -num)  # 최대 힙 (음수 저장)
    heapq.heappush(min_heap, num)   # 최소 힙 (그대로 저장)
    valid[num] = valid.get(num, 0) + 1  # 값 추가 (유효성 체크)

• 최소 힙과 최대 힙에 동시에 삽입합니다.
• valid 딕셔너리를 이용해 해당 숫자가 큐에 몇 번 추가되었는지 카운트합니다.

---

3.2.2. 삭제 연산 (D 1 또는 D -1)

elif cmd == "D":
    if num == 1:  # 최대값 삭제
        while max_heap:
            max_val = -heapq.heappop(max_heap)  # 최대 힙에서 가장 큰 값 꺼내기
            if valid.get(max_val, 0) > 0:  # 실제 유효한 값인지 확인
                valid[max_val] -= 1
                break

• max_heap에서 최댓값을 꺼냅니다.
• valid에 유효한 값이 있을 경우, valid 값을 감소시키고 삭제합니다.
• valid[max_val] == 0이면 이미 다른 연산에서 삭제된 값이므로 무시하고 다음 값을 가져옵니다.

    elif num == -1:  # 최소값 삭제
        while min_heap:
            min_val = heapq.heappop(min_heap)  # 최소 힙에서 가장 작은 값 꺼내기
            if valid.get(min_val, 0) > 0:  # 실제 유효한 값인지 확인
                valid[min_val] -= 1
                break

• min_heap에서 최솟값을 꺼내고 유효성을 검사하여 삭제합니다.

---

3.3. 최종 결과 정리

while max_heap and valid.get(-max_heap[0], 0) == 0:
    heapq.heappop(max_heap)

while min_heap and valid.get(min_heap[0], 0) == 0:
    heapq.heappop(min_heap)

• 삭제된 값이 max_heap 또는 min_heap의 최상단에 남아 있을 수 있으므로 유효한 값만 남길 때까지 제거합니다.

if not max_heap or not min_heap:
    print("EMPTY")
else:
    print(-max_heap[0], min_heap[0])  # 최대값, 최소값 출력

• 힙이 비어 있다면 "EMPTY"를 출력합니다.
• 비어 있지 않다면 최댓값과 최솟값을 출력합니다.

 

---

4. 시간 복잡도 분석

• 삽입 연산 (I n) : O(log K)
• 삭제 연산 (D 1 또는 D -1) : O(log K)
• 유효성 검사 및 정리 : O(K)
• 총 연산 횟수 (K) : 최대 100만이므로 O(K log K)의 시간 복잡도를 가집니다.

 

---

5. 예제 실행

입력 예시

2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333

출력 예시

EMPTY
333 333

 

---

6. 마무리

 

✅ Lazy Deletion 사용 → 불필요한 연산 감소
✅ 두 개의 힙을 동기화 → 빠른 삭제 구현
✅ 딕셔너리를 활용한 유효성 체크 → 불필요한 삭제 방지

 

이 문제는 힙(Heap)과 해시맵(HashMap)의 조합을 활용하는 대표적인 문제입니다.
이중 우선순위 큐를 직접 구현할 일이 있다면, 두 개의 힙과 Lazy Deletion 기법을 떠올리면 좋습니다.

💡 비슷한 유형의 문제

• 프로그래머스 - 이중우선순위큐 (https://school.programmers.co.kr/learn/courses/30/lessons/42628)

 

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.