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

제목부터 힙큐 두개쓰라고 나와서 두개썼다.

근데 사실 큐를 두개쓰기때문에 한쪽에서 사라진걸 다른쪽에서 어떻게 없앨꺼냐? 에 대한 아이디어를 보는 문제였다.

결론은 삽입시 입력했던 i값이 같은 인자를 매번 D패턴마다 앞에서 while을 통해 삭제시켜주는 것.

겹쳤던걸 모두 거른 후 본 명령을 시행하는 방식이다. i값 삭제여부는 삽입시 true 삭제시 false로

공유되는 정보인 visited 배열을 통해 해결한다.

=> 연결되지 않는 두 자료구조 간에는 id값과 공통정보를 수용하는 자료구조를 두어 연계시킨다.

import sys
input = sys.stdin.readline
from heapq import heappush,heappop

# key값 관리를 통해 어떤 수를 삽입하면 True 삭제하면 그 키값을 False로 바꿔서 반대편 힙에서 맨앞에 삭제한 수가 나왔을때 미리 
#  삭제를 해주고 삭제연산을 시작한다.
T = int(input())
for test in range(T):
    k = int(input())
    max_heap=[]
    min_heap=[]
    visited = [False] * 1000001
    for i in range(k):
        command,n = input().split()
        n=int(n)
        if command=='D':
            if n==1:
                while max_heap and not visited[max_heap[0][1]]:
                    heappop(max_heap)
                if max_heap:
                    visited[max_heap[0][1]] = False
                    heappop(max_heap)
            else:
                while min_heap and not visited[min_heap[0][1]]:
                    heappop(min_heap)
                if min_heap:
                    visited[min_heap[0][1]] = False
                    heappop(min_heap)
        else:
            heappush(max_heap,(-n,i))
            heappush(min_heap,(n,i))
            visited[i] = True
    while max_heap and not visited[max_heap[0][1]]:
        heappop(max_heap)
    while min_heap and not visited[min_heap[0][1]]:
        heappop(min_heap)

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