BOJ-7662 이중 우선순위 큐

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

문제 소개

이중 우선순위 큐는 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료구조이며 삭제 시 우선순위가 가장 높은 데이터와 가장 낮은 데이터를 선택하여 삭제가 가능하다.

정수만 저장하는 이중 우선순위 큐가 있을 때, 일련의 연산을 진행한 후 최종적으로 이중 우선순위 큐에 저장된 데이터 중 최대값과 최소값을 출력하는 프로그램을 출력한다.

문제 풀이

변수 t는 테스트 데이터의 개수이고 변수 k는 해당 테스트 케이스에서 적용할 연산의 개수이다.

최소 힙과 최대 힙을 각각 둔 다음, 두 힙에 저장되는 데이터의 동기화를 위해 딕셔너리형 변수 d를 두어 True/False로 해당 데이터가 실재하는지 여부를 나타내었다.

데이터를 추가할 때는 두 힙에 동시에 추가하고 해당 데이터에 대해 d를 True로 플래그한다.

데이터를 삭제할 때는 아래의 과정을 따른다.

1. 최대값(최소값)을 삭제하는 경우 최대 힙(최소 힙)에서 pop을 하기 전에 가장 우선순위가 높은 데이터가 최소 힙(최대 힙) 쪽에서 이미 삭제한 원소인지 확인한다. 만약 이미 삭제된 데이터라면 여기서도 pop한다.

2. 삭제되지 않은 데이터가 나오거나 최대 힙(최소 힙)이 빌 때까지 과정 1.을 반복한다.

   1. 삭제되지 않은 데이터가 나왔다면 해당 데이터에 대해 d를 False로 플래그하고 pop한다.

   2. 힙이 빈 상태가 되었다면 아무 일도 하지 않는다.

k번의 연산이 끝나고 나면 두 힙에서 각각 이미 삭제된 원소가 있다면 pop한다. 이 과정이 필요한 이유는 데이터의 삭제가 두 힙에서 동시에 이루어지지 않기 때문이다.

마지막 삭제 연산이 최대갑 삭제였다면 최소 힙에는 삭제된 값이 그대로 남아있게 되며, 반대의 경우에도 마찬가지이다.

많은 삽입 연산을 한 후, 최대 힙에서만 모든 데이터를 삭제했다고 생각해 보자. 최대 힙은 비어 있지만 최소 힙은 데이터들을 아직 삭제하지 못했으므로 모든 데이터가 추가된 그대로 남아있을 것이다.

마지막으로 힙에 데이터가 있는 경우 최대값과 최소값을 차례로 출력하고, 힙이 비어있다면 EMPTY를 출력한다.

코드

from sys import stdin
import heapq
input = lambda: stdin.readline().rstrip()

t = int(input())
for _ in range(t):
    k = int(input())
    # 최소 힙과 최대 힙
    heap_max = []
    heap_min = []
    # 실재 여부를 나타내는 딕셔너리
    d = dict()
    for i in range(k):
        data = input().split()
        op, num = data[0], int(data[1])
        # 삽입 연산
        if op == 'I':
            heapq.heappush(heap_max, (-num, i))
            heapq.heappush(heap_min, (num, i))
            d[i] = True
        # 최대값 삭제 연산
        elif num == 1:
            # 힙이 비지 않았고 이미 삭제된 데이터가 pop되는 한 반복
            while heap_max and not d[heap_max[0][1]]:
                heapq.heappop(heap_max)
            # 실제하는 데이터 pop
            if heap_max:
                d[heap_max[0][1]] = False
                heapq.heappop(heap_max)
        # 최소값 삭제 연산
        else:
            # 힙이 비지 않았고 이미 삭제된 데이터가 pop되는 한 반복
            while heap_min and not d[heap_min[0][1]]:
                heapq.heappop(heap_min)
            # 실제하는 데이터 pop
            if heap_min:
                d[heap_min[0][1]] = False
                heapq.heappop(heap_min)

        # 이미 삭제된 데이터 처리
        while heap_max and not d[heap_max[0][1]]:
            heapq.heappop(heap_max)
        while heap_min and not d[heap_min[0][1]]:
            heapq.heappop(heap_min)

    # 결과 출력
    if heap_max:
        print(-heap_max[0][0], heap_min[0][0])
    else:
        print("EMPTY")

아래의 포스팅을 참고하였습니다.

https://neomindstd.github.io/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/boj7662/