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

백준 7662 이중 우선순위 큐

두 개의 우선순위 큐를 활용하고 남은 요소들의 갯수를 공유하는 아이디어는 금방 잘 떠올렸지만, 구현하는 과정에서 defaultdict를 사용했다가 시간 초과가 났다. 방문했는지 저장하는 배열이 더 효율적이지만, 떠올리지 못했다.

1. 두 개의 큐를 활용한다(최댓값, 최솟값)
2. 큐에 삽입할 때, 입력받은 순서(index)도 같이 저장한다.
3. 제거할 때, 입력받은 순서(index)를 활용해 제거했는지 확인하고, 제거했다면, 제거하지 않은 숫자가 나올 때까지 반복한다.
4. 숫자를 제거한다.

정답 코드

import sys
import heapq

for T in range(int(sys.stdin.readline())):
    k = int(sys.stdin.readline())
    removed = [False] * k
    maxH, minH = [], []
    for i in range(k):
        op, n = sys.stdin.readline().split()
        n = int(n)

        if op == 'I':
            heapq.heappush(minH, (n, i))
            heapq.heappush(maxH, (-n, i))
            removed[i] = True
        elif n == 1:
            while maxH and not removed[maxH[0][1]]:
                heapq.heappop(maxH)
            if maxH:
                removed[maxH[0][1]] = False
                heapq.heappop(maxH)
        else:
            while minH and not removed[minH[0][1]]:
                heapq.heappop(minH)
            if minH:
                removed[minH[0][1]] = False
                heapq.heappop(minH)
    while minH and not removed[minH[0][1]]:
        heapq.heappop(minH)
    while maxH and not removed[maxH[0][1]]:
        heapq.heappop(maxH)
    print(-maxH[0][0], minH[0][0]) if maxH and minH else print("EMPTY")

나의 코드

import sys
from collections import defaultdict
from queue import PriorityQueue

input = sys.stdin.readline
d = defaultdict(int)
spq = PriorityQueue()
bpq = PriorityQueue()

for _ in range(int(input().strip())):
    for __ in range(int(input().strip())):
        s, n = input().split()
        if s == "I":
            n = int(n)
            d[n] += 1
            spq.put(n)
            bpq.put(-1 * n)
        else:
            if n == "1":
                tmp = -1 * bpq.get()
                while not bpq.empty() and d[tmp] == 0:
                    tmp = -1 * bpq.get()
            else:
                tmp = spq.get()
                while not spq.empty() and d[tmp] == 0:
                    tmp = spq.get()
            if d[tmp] != 0:
                d[tmp] -= 1
    tmp = -1 * bpq.get()
    while not bpq.empty() and d[tmp] == 0:
        tmp = -1 * bpq.get()
    if bpq.empty():
        print("EMPTY")
        continue
    print(tmp, end = " ")
    tmp = spq.get()
    while not spq.empty() and d[tmp] == 0:
        tmp = spq.get()
    print(tmp)