[Python] 백준 7662번 문제, 이중 우선순위 큐

<문제 링크>

 

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

7662번: 이중 우선순위 큐

 

---

<풀이>

 

이중 우선순위 큐를 큐 한 개만 이용해서 풀려고 했는데 안 됐다...

최소힙이 기준인 heapq 라이브러리를 이용해도 0-index가 최소값이기 때문에 반대편인 len(que)-1-index가 최대값일 것이라고 생각했다.

하지만 아니였다.

최소힙 기준으로 정렬되는 것이기 때문에 뒷부분에서 최대값들로 정렬된다는 보장이 없기 때문이다.

 

그렇기 때문에 최대힙과 최소힙으로 이루어진 우선순위 큐가 필요하다.

그런데 heapq은 최소힙만 지원하기 때문에 여기서 트릭을 하나 사용해야 한다.

부호를 무시하고 값만 따져서 저장되게 하기 위해 최대힙에 값을 삽입할 때 - 부호를 붙여서 넣는다.

그러면 음수는 양수가 되어 뒤로 밀리고 양수는 음수가 되며, 제일 큰 양수가 제일 작은 음수가 되어 최대힙처럼 작동한다.

또한, 값을 넣어줄 때 동기화를 위해 튜플로 (value, id) 방식으로 넣어 준다.

 

삽입은 위와 같은 방법으로 하면 되는데 삭제는 어떻게 해야 하는가?

두 개의 큐를 사용하기 때문에 큐 안에 있는 값들을 동기화시켜줘야 할 필요가 있다.

그래서 id를 이용해 True면 큐 안 에 있는 값이며, False는 큐에 없는 값이다.

그래서 삭제를 수행할 때, 동기화 후에 삭제를 진행한다.

sync() 메소드에서 내가 가지고 있는 최대값 혹은 최소값이 반대 큐에서 삭제가 됐다면 자신의 큐에서도 삭제한다.

그런 다음에 삭제 작업을 수행하는데 id[q의 id]를 False를 만든 후에 q에서 heapq.pop()해준다.

 

마지막으로 출력하기 전에 동기화를 진행해주고 큐가 비어있다면, "EMPTY"를 출력하고 그렇지 않다면 큐에서 0번째 인덱스(value, id)의 value를 출력해준다.

(* max_que에 삽입 시에 - 부호를 넣어 줬기 때문에 출력할 때 -를 붙여줘야 한다.)

 

---

<코드>

*sync(q): q를 동기화하는 메소드

id: 동기화 여부를 체크하기 위한 아이디

(k <= 1,000,000 이기 때문에 id.length == 1,000,000)

max_que, min_que: 최대값, 최소값을 구하기 위한 우선순위 큐

---

import heapq
import sys
input = sys.stdin.readline


# 동기화 메소드
def sync(q):
    # min_que, max_que 동기화
    while q and not id[q[0][1]]:
        heapq.heappop(q)

if __name__ == "__main__":
    for T in range(int(input())):
        k = int(input())
        max_que, min_que = [], []
        id = [False] * 1000001 # 동기화 아이디

        for i in range(k):
            order, num = input().split()

            if order == 'I':
                # input
                heapq.heappush(min_que, (int(num), i))
                heapq.heappush(max_que, (-int(num), i))
                id[i] = True
            elif num == '1':
                sync(max_que)

                # 최대값 삭제
                if max_que:
                    id[max_que[0][1]] = False
                    heapq.heappop(max_que)
            else:
                sync(min_que)

                # 최소값 삭제
                if min_que:
                    id[min_que[0][1]] = False
                    heapq.heappop(min_que)

        sync(min_que)
        sync(max_que)

        # print
        if max_que and min_que:
            print(-max_que[0][0], min_que[0][0])
        else:
            print("EMPTY")