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

📜 접근 방법

I n : n 삽입

D -1 : 최소값 삭제

D 1 : 최댓값 삭제

 

최댓값과 최솟값을 넣는 배열을 만들고 삽입 시 두 배열에 넣어주는데 인덱스와 함께 넣어준다.

또한 check_num으로 숫자를 삭제했는지 확인하는 배열로 삽입시에는 True로 변경하고 삭제시엔 False로 변경한다.

-> 이렇게 하는 이유는 최솟값과 최댓값을 삭제할 시에 어떤 값을 삭제했는지 서로 모르기 때문이다.

 

❌ 실패 코드

삭제시에 양쪽 우선순위 큐에서 동시에 같은 값을 삭제를 하려고 해서 풀지 못했다.

 

✅ 정답 코드

import sys
import heapq

t = int(sys.stdin.readline())

for i in range(t):
    max_heap = []
    min_heap = []

    n = int(sys.stdin.readline())

    check_num = [False] * n

    for num_index in range(n):
        w, num = sys.stdin.readline().split()
        num = int(num)

        if w == "I":
            # 값 삽입
            heapq.heappush(min_heap, (num, num_index))
            heapq.heappush(max_heap, (-num, num_index))
            check_num[num_index] = True

        elif w == "D":
            if num == 1:
                # 최대값 삭제
                while max_heap:
                    output, index = heapq.heappop(max_heap)
                    if check_num[index] == True:
                        check_num[index] = False
                        break
            elif num == -1:
                # 최소값 삭제
                while min_heap:
                    output, index = heapq.heappop(min_heap)
                    if check_num[index] == True:
                        check_num[index] = False
                        break

    while min_heap and check_num[min_heap[0][1]] == False:
        heapq.heappop(min_heap)
    while max_heap and check_num[max_heap[0][1]] == False:
        heapq.heappop(max_heap)

    if min_heap and max_heap:
        print(-max_heap[0][0], min_heap[0][0])
    else:
        print("EMPTY")

💡알게 된점

2개의 우선순위 큐를 사용하는 것은 알았는데 삭제시에 양쪽 우선순위 큐에서 동시에 같은 값을 삭제를 해줘야하는데 그부분을 어떻게 짜야할지 어려웠다.