[골드 4] 백준 7662 - 이중 우선순위 큐 (파이썬)

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

풀이

• I x : x를 삽입
• D 1 : 최댓값 삭제
• D -1 : 최솟값 삭제
• 최종적으로 큐에 남아 있는 값 중 최댓값과 최솟값 출력
• 비어 있으면 "EMPTY" 출력

min_pq = PriorityQueue()  # 최소 힙
max_pq = PriorityQueue()  # 최대 힙 (음수로 삽입)
count = {}  # 실제 유효한 값 카운트

• 이중 우선순위 큐를 min_pq, max_pq로 나눠서 관리한다
• 동기화가 되지 않기 때문에, 실제 삭제 여부는 count 딕셔너리로 관리한다.

if t == 'I' :
    min_pq.put(v)
    max_pq.put(-v)
    count[v] = count.get(v, 0) + 1

• 삽입 연산의 경우 우선순위 큐에 put을 이용해서 최소, 최대 힙을 생성한다.

if t == 'D' :
    if v == 1:  # 최대값 삭제
        while max_pq.qsize() != 0 :
            x = -max_pq.get()
            if count.get(x, 0) != 0 :
                count[x] -= 1
                break
    elif v == -1:  # 최소값 삭제
        while min_pq.qsize() != 0 :
            x = min_pq.get()
            if count.get(x, 0) != 0 :
                count[x] -= 1
                break

삭제 연산의 경우 실제 삭제는 count가 0이 아닌 원소만 수행하고, 삭제된 원소들은 큐에 남아 있을 수 있으므로 지연 삭제 방식을 사용한다.

max_val = -1e12
min_val = 1e12

# 유효한 최댓값 찾기
while max_pq.qsize() != 0 :
    x = -max_pq.get()
    if count.get(x, 0) != 0 :
        max_val = x
        break

# 유효한 최솟값 찾기
while min_pq.qsize() != 0 :
    x = min_pq.get()
    if count.get(x, 0) != 0:
        min_val = x
        break

출력의 경우, 둘다 찾지 못한 경우는 EMPTY를 출력하고, 찾은 경우 max_val, min_val을 출력한다.

코드

# 백준 7662 - 이중 우선 순위 큐
# 분류 : 우선 순위 큐

import sys
from queue import PriorityQueue

input = sys.stdin.readline

T = int(input())

for _ in range(T) :
    Q = int(input())

    min_pq = PriorityQueue()
    max_pq = PriorityQueue()
    count = {}

    for _ in range(Q) :
        t, v = input().split()
        v = int(v)

        if t == 'I' :
            min_pq.put(v)
            max_pq.put(-v)
            if v not in count :
                count[v] = 0
            count[v] += 1
        if t == 'D' :
            if v == 1 :
                while max_pq.qsize() != 0 :
                    x = -max_pq.get()
                    if count[x] != 0 :
                        count[x] -= 1
                        break
            if v == -1 :
                while min_pq.qsize() != 0 :
                    x = min_pq.get()
                    if count[x] != 0 :
                        count[x] -= 1
                        break
    max_val = -1e12
    min_val = 1e12

    while max_pq.qsize() != 0 :
        x = -max_pq.get()
        if count[x] != 0 :
            max_val = x
            break
    
    while min_pq.qsize() != 0 :
        x = min_pq.get()
        if count[x] != 0:
            min_val = x
            break
    
    if max_val == -1e12 :
        print("EMPTY")
    else :
        print(max_val, min_val)