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

📜 접근 방법

1. 최소힙, 최대힙 2개 사용 -> 실패

2. 추가로 숫자를 체크하는 배열 사용 -> 성공

 

n 만큼 배열을 추가 : 숫자가 힙에 들어왔는지 체크하는 배열이며, 기본값은 False

 

처음에는 최소힙과 최대힙에 숫자만 넣어줬다면

튜플로 인덱스를 함께 넣어줌 -> heapq.heappush(min_heap, (num, num_index))

인덱스는 값이 들어오는 순서(0 ~ n-1)

 

- 숫자를 추가할 경우 False -> True로 변경 (True이면 값이 힙 안에 존재한다는 것)

- 숫자를 제거할 경우 힙 안에 들어있는 최소(최대)값을 찾아서 제거해줘야하는데 그 부분을 배열에서 체크해야함!

현재 힙에 들어있는 최대, 최소값을 찾기 위해 pop을 시킨 후 그 값의 index와 배열의 인덱스를 확인하여 True값을 찾아야함

 

 

그 후 힙에 남아 있는 최소값과 최대값 출력

-> pop을 하여 배열이 True인 것을 찾으면 됨

 

 

❌ 실패 이유

최소힙, 최대힙 2개만 사용하려 하니 pop된 숫자를 최소힙과 최대힙에서 구분하지 못해 실패

-> 숫자를 체크하는 배열을 추가했다.

 

 

✅ 정답 코드

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")

💡알게 된점

 

최소힙과 최대힙만 사용하여 문제를 풀려고하니 풀리지 않아, 이와 비슷한 문제가 주어질 경우 숫자 체크하는 배열을 사용하는 방법도 생각해봐야겠다.