[백준] 7662번 이중 우선 순위 큐(python)

마뇽미뇽·2026년 3월 5일

백준 알고리즘

알고리즘 문제풀이

목록 보기

168/169

1. 문제

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

📚 알고리즘 분류 : 구현 (자료구조 힙)

2. 풀이

초기 풀이

힙을 통한 최소힙 구현 후 D == 1 일때, D == -1 일때 최대 최소를 뽑는 조건으로 구현하였다.

import sys
import heapq

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    q = int(input())
    heap = []
    for i in range(q):
        temp = input().split()
        char = temp[0]
        num = int(temp[1])

        if not heap and char == 'D':
            continue

        if char == 'I':
            heapq.heappush(heap, num)

        elif char == 'D':
            if num == 1:
                heap.remove(heap[-1])
            elif num == -1:
                heapq.heappop(heap)

    if not heap:
        print("EMPTY")
    else:
        print(heap[-1], heap[0])

remove를 활용해서 시간 초과가 났다 (복잡도 O(n))
추가적으로 최소 힙만을 구현했기 때문에 최소값은 보장하지만 이후 heap[-1]이 힙에서 항상 최댓값을 보장하지 못한다는 문제점을 발견하였다.

변경한 방식

최대 힙과 최소 힙을 구현하는 방식으로 전환했다. 그러나 최대힙은 마지막이 항상 최소값을, 최소힙은 마지막이 항상 최대값을 보장하지 못한다는 문제는 여전했다.
이를 해결하고자 인덱스를 추가함으로써 삭제여부를 확인할 수 있는 딕셔너리를 추가하였다.
https://sdsf1225.tistory.com/83 님을 참고하였다.

3. 코드

import sys
import heapq

input = sys.stdin.readline

t = int(input().strip())

for _ in range(t):
    q = int(input().strip())

    min_heap = []
    max_heap = []
    dic = dict()

    for i in range(q):
        temp = input().strip().split()

        char = temp[0]
        num = int(temp[1])

        if char == 'I':
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap, -num)
            if num in dic.keys():
                # 중복 갯수 존재 표시
                dic[num] += 1
            else:
                # 개수 1개 들어감 표시
                dic[num] = 1

        elif char == 'D':
            if num == 1:
                while max_heap:
                    # 이 값은 삭제된 값이라는 것을 알려줌
                    if dic[-max_heap[0]] == 0:
                        heapq.heappop(max_heap)
                    else:
                        break

                # 안에 최댓값을 찾아야하니까 갯수 1개 제거
                if max_heap:
                    dic[-heapq.heappop(max_heap)] -= 1

            elif num == -1:
                while min_heap:
                    if dic[min_heap[0]] == 0:
                        heapq.heappop(min_heap)
                    else:
                        break

                if min_heap:
                    dic[heapq.heappop(min_heap)] -= 1

    # 비어있는 경우가 아니라면 최대, 최소를 찾아야하므로 재확인
    while max_heap:
        if dic[-max_heap[0]] == 0:
            heapq.heappop(max_heap)
        else:
            break

    while min_heap:
        if dic[min_heap[0]] == 0:
            heapq.heappop(min_heap)
        else:
            break

    if not min_heap:
        print("EMPTY")
    else:
        max_num = -heapq.heappop(max_heap)
        min_num = heapq.heappop(min_heap)

        print(max_num, min_num)