이중 우선순위 큐

데이터들 중에서 최솟값과, 최댓값을 지속적으로 탐색해 선택적으로 제거하고 싶을 때 우선순위 큐를 활용해서 구현할 수 있다. 이때 최솟값과 최댓값 두 종류의 동작이 있기 때문에 이중 우선순위 큐라고 부를 수 있을 것이다.

😛 프로그래머스 문제를 살펴보자

⭐ 프로그래머스

• https://school.programmers.co.kr/learn/courses/30/lessons/42628

from heapq import heappop, heappush
def solution(operations):
    h = []
    for data in operations:
        ID, num = data.split()
        if ID == "I" : heappush(h, int(num))
        elif ID == "D" and h and num == "-1" : heappop(h)
        elif ID == "D" and h and num == "1" :
            h.remove(max(h))

    if not h : return [0,0]
    else : 
        return [max(h),h[0]]

⏩ heap list를 하나만 사용을 했다.
⏩ 최솟값은 heappop으로 제거가 가능하다.
⏩ 최댓값은 remove 함수를 이용해서 제거했다.

💯 heap은 트리구조로 되어 있기 때문에 heap만을 활용하면 효율성이 좋으나, remove와 같은 내장함수를 사용하게 될 경우 효율성을 많이 떨어뜨릴 수 있다.

😛 백준 문제에서 이를 개선해보자

⭐ 백준

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

import sys
from heapq import heappop, heappush

input = sys.stdin.readline

for TC in range(int(input())):
    K = int(input())
    min_h, max_h = [], []
    
    // 삭제 여부를 판단하는 visited배열을 생성해준다.
    vi = [0] * K 

    for k in range(K):
        ID, num = map(str, input().split())
        if ID == "I":
        	// 해당 숫자(num)가 몇 번째(k)에 들어왔는지도 함께 push
            heappush(min_h, (int(num),k))
            heappush(max_h, (-int(num),k))
            
            // k 번째 들어온 숫자 = 1
            // 1 : k번째 숫자는 아직 존재한다.
            // 0 : k번째 숫자는 삭제된 숫자다.
            vi[k] = 1
        else:
            if num == "-1":
                while min_h and not vi[min_h[0][1]]: heappop(min_h)
                if min_h: vi[heappop(min_h)[1]] = 0
            elif num == "1":
                while max_h and not vi[max_h[0][1]]: heappop(max_h)
                if max_h: vi[heappop(max_h)[1]] = 0

        while min_h and not vi[min_h[0][1]]: heappop(min_h)
        while max_h and not vi[max_h[0][1]]: heappop(max_h)

    if min_h :
        print(-max_h[0][0], min_h[0][0])
    else:
        print("EMPTY")

⏩ vi배열을 활용을해서 해당 숫자가 들어온 차례로 삭제된 것인지 아닌지 판단해준다.
⏩ vi[?] = 0 이면 삭제된 숫자이니 min_h, max_h에서 전부 삭제해준다.
⏩ vi[?] = 1 은 아직 존재한다는 의미
⏩ 이렇게 하면 heap 자료구조만을 활용하여 구할 수 있기 때문에 효율성측면에서 아주 좋다.

💯 이것도 내가 직접 해결못했는데, vi배열이라는 아주 친숙한 도구를 활용할 생각을 못해낸게 참 아쉽다.