[Python] 백준/BOJ 7662번: 이중 우선순위 큐 (Gold 4)

💻 Problem

문제 보러 가기

 

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

 

💡 Approach

어려웠담..

 

처음에는 heap 리스트를 하나만 선언했다.

최댓값 삭제 전후에 heap 안의 모든 원소들에 -1을 곱하고 heapify로 다시 힙으로 만들어줬다.

이건 당연히 시간초과 났다..

그래서 최대 힙과 최소 힙을 따로 선언해야겠다고 생각했다.

 

따로 선언하고 보니 최대힙에서 최댓값을 삭제해도 최소 힙에는 반영이 안 돼서 문제가 생겼다.

최대 힙에서 이미 삭제한 원소를 최소 힙에서 이중으로 삭제하려는 문제가 있었담..

이 문제를 어떻게 해결해야 할지 고민하다가 결국 모르겠어서 찾아봤다 ㅠ-ㅠ

 

여러 방법이 있지만 딕셔너리를 선언해서 방문 처리(유효 처리)하는 방법이 이해하기 쉬웠다.

삽입 명령을 입력받을 때의 번호를 key로 사용하여 유효성을 True로 추가한다.

삭제 명령을 입력받으면 삭제하려는 힙(최댓값 삭제면 최대 힙, 최솟값 삭제면 최소 힙)의 sync를 맞춘다.

• sync 맞춘다 = 삭제한 값을 동기화한다
• 예를 들어, 최대 힙 = [(-8, 7), (-7, 5), (-6, 6), (-1, 0)] 최소 힙 = [(5, 1), (6, 2), (6, 6), (7, 5), (8, 7)] 일 때, 최솟값 삭제를 하려고 한다.
• 최소 힙만 보면 5를 삭제할 차례처럼 보이지만, 5는 이미 최대 힙에서 삭제한 값이고, 실제로는 6을 삭제할 차례이다.
• 이때, sync를 맞춰야 한다.
• 원소 5의 key 값은 1이므로 visited[1]을 확인하면 False일 것이다.
• 이렇게 최소 힙의 첫 번째 값을 보고 유효하지 않으면 계속 heappop을 한다.
• (최대 힙 <-> 최소 힙 반대 상황도 마찬가지)

sync를 맞췄으면 이제 삭제하려는 원소의 key 유효성을 False로 체크하고, heappop을 한다.

 

모든 명령 이후에 최대 힙, 최소 힙 모두 sync를 맞춰주고 최대 힙에서 첫 번째 값과 최소 힙에서 첫 번째 값을 출력한다.

 

✏️ Solution

import sys
import heapq
input = sys.stdin.readline

def sync(heap):
    # 유효하지 않은 원소 삭제
    while heap and not visited[heap[0][1]]:
        heapq.heappop(heap)

t = int(input())

for _ in range(t):
    k = int(input()) # Q에 적용할 연산의 개수
    minheap = [] # 최소 힙 (최솟값 추출용)
    maxheap = [] # 최대 힙 (최댓값 추출용, 음수 저장)
    visited = {} # 삽입된 원소의 유효 여부 체크 (key: 인덱스, value: 유효 여부)

    for key in range(k):
        command, n = input().split()

        # I n: 정수 n을 Q에 삽입
        if command == 'I':
            heapq.heappush(minheap, (int(n), key))
            heapq.heappush(maxheap, (-int(n), key))
            visited[key] = True

        elif command == 'D':
            # D 1: Q에서 최댓값 삭제
            if n == '1':
                sync(maxheap)
                if maxheap:
                    # 삭제하려는 원소의 key 유효 체크
                    visited[maxheap[0][1]] = False
                    heapq.heappop(maxheap)

            # D -1: Q에서 최솟값 삭제
            elif n == '-1':
                sync(minheap)
                if minheap:
                    # 삭제하려는 원소의 key 유효 체크
                    visited[minheap[0][1]] = False
                    heapq.heappop(minheap)
    
    sync(minheap)
    sync(maxheap)
    
    if minheap and maxheap:
        print(-maxheap[0][0], minheap[0][0])
    else:
        print('EMPTY')

• 시간복잡도: O(k log k) = O(10^6 * 20) = 2 * 10^7