[알고리즘][Python] 백준 7662 이중 우선 순위 큐 문제 풀이

문제 출처 : www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

---

문제 해석 : 이중 우선 순위 큐를 구현하는 문제이다. 여기서 주의할 점은 최대, 최소 힙의 역활을 동시에 수행해야 한다는 것이다.

 

문제 풀이 : 파이썬에서는 heapq를 제공하고 있기 때문에 이를 이용하기로 한다. 2개의 heapq를 생성하고 하나는 최대힙으로 하나는 최소힙으로 사용하면서 삭제 연산에 있어서 동기화를 위해서 sync라는 배열을 통해서 삭제시 동시에 삭제를 보장한다.  -> remove 같은 내장 함수를 사용하는 것보다 이런 식으로 별도의 id를 사용하는 것이 더욱 빠른 연산이 가능하다.

---

풀이 코드

import heapq
def sync(arr):
    while arr and id[arr[0][1]] == 0:
        heapq.heappop(arr)

T = int(input())
for test_case in range(T):
    max_arr = []
    min_arr = []
    id = [0] * 1000000
    K = int(input())
    count = 0
    for i in range(K):
        S, num = input().split()

        if S == "I":
            heapq.heappush(max_arr, (-1 * int(num), i))
            heapq.heappush(min_arr, (int(num),i))
            id[i] = 1
            
        else:

            if num == "1":
                sync(max_arr)
                if max_arr:
                    id[max_arr[0][1]] = 0
                    heapq.heappop(max_arr)

            elif num == "-1":
                sync(min_arr)
                if min_arr:
                    id[min_arr[0][1]] = 0
                    heapq.heappop(min_arr)

    sync(max_arr)
    sync(min_arr)

    if len(max_arr) == 0:
        print("EMPTY")
    else:
        print(-1 * max_arr[0][0], end =" ")
        print(min_arr[0][0])

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.