[BOJ] 7662. 이중 우선순위 큐(python)

📌문제

💪아이디어

1. 이중순위 큐 만들기
   min heap이나 max heap의 맨 마지막 인덱스의 값이 max, min값이라 생각할 수 있지만 그렇지 않다. 그래서 한 가지 종류의 heap만 가지고는 최대값과 최소값을 다룰 수 없다.
   

2. 값 체크하기
   min heap과 max heap 모두 만들어 중복된 숫자가 입력될 수 있기 때문에 인덱스값을 체크기준으로 두고 그 값이 삭제되었는지 체크한다.
   

🥂코드

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

def dual(heap,chk):
    if heap:
        while not visited[heap[0][1]]:
            heappop(heap)
        if chk:
            visited[heap[0][1]]=False
            heappop(heap)

T = int(input())
for _ in range(T):
    max_heap, min_heap = [], []
    k = int(input())
    visited = [False]*k 
    for i in range(k):
        c, n = input().split()
        n=int(n)
        if c == "I": 
            heappush(min_heap,(n,i))
            heappush(max_heap,(-n,i))
            visited[i]=True
        else:
            if n == -1: dual(min_heap,1)
            else: dual(max_heap,1)
    dual(min_heap,0)
    dual(max_heap,0)
    if min_heap and max_heap: 
        print(-1*heappop(max_heap)[0],heappop(min_heap)[0])
    else: print("EMPTY")