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

문제

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

 

풀이

1. 단순히 deque과 sort(O(N * log N))를 이용하여 이중 우선순위 큐를 모사할 시 시간 초과 발생

2. heapq는 O(logN)으로 시간 초과 발생 X, 하지만 최대 힙, 최소 힙을 유지하면서 max, min 제거와 동기화를 같이 해줘야 함.

3. default dict 사용 -  I로 들어온 val에 대해 관리. D로  삭제 시 반영. >> 최대 힙, 최소 힙 동기화
    - idx로 구분하여 관리하기에 중복 값에 대한 관리 가능.

from heapq import heappush, heappop
from collections import defaultdict

input = __import__('sys').stdin.readline

t = int(input())

for _ in range(t):
    min_h = []
    max_h = []
    visited = defaultdict(bool)
    idx = 0

    for _ in range(int(input())):
        cmd, val = input().split()
        val = int(val)

        if cmd == 'I':
            heappush(min_h, (val, idx))
            heappush(max_h, (-val, idx))
            visited[idx] = True
            idx += 1
        else:
            if val == 1:
                while max_h and not visited[max_h[0][1]]:
                    heappop(max_h)
                if max_h:
                    visited[max_h[0][1]] = False
                    heappop(max_h)
            else:
                while min_h and not visited[min_h[0][1]]:
                    heappop(min_h)
                if min_h:
                    visited[min_h[0][1]] = False
                    heappop(min_h)

    while min_h and not visited[min_h[0][1]]:
        heappop(min_h)
    while max_h and not visited[max_h[0][1]]:
        heappop(max_h)

    if not min_h or not max_h:
        print("EMPTY")
    else: 
        print(f"{-max_h[0][0]} {min_h[0][0]}")