📌 Problem.

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

최대/최소 모두에 접근 가능한 이른바 '이중 우선순위 큐'(Q)를 구현한다.
I n     :  n을 삽입한다.
D -1  :  최솟값을 삭제한다.
D 1    :  최댓값을 삭제한다.

📌 Solution.

1. 삽입 데이터에 id 값 부여

import sys
import heapq

input = sys.stdin.readline

for _ in range(int(input())):
    k = int(input())
    exist = [0] * k
    min_heap = []
    max_heap = []

    def clear(heap):
        while heap and not exist[heap[0][1]]:
            heapq.heappop(heap)

    """ execute the commands """
    for key in range(k):
        command = input().split()
        # I n
        if command[0] == 'I':
            heapq.heappush(min_heap, (int(command[1]), key))
            heapq.heappush(max_heap, (-int(command[1]), key))
            exist[key] = 1
        # D -1
        elif command[1] == '-1':
            clear(min_heap)
            if min_heap:
                exist[heapq.heappop(min_heap)[1]] = 0
        # D 1
        else:
            clear(max_heap)
            if max_heap:
                exist[heapq.heappop(max_heap)[1]] = 0
                
    clear(min_heap)
    clear(max_heap)

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

삽입되는 값들은 key라는 id와 함께 튜플로 삽입된다.
가령, 한 테스트케이스에서 'I 3', 'I 7', 'I 3'이 순서대로 입력된다면 각각 (3, 0), (7, 1), (3, 2)로 힙에 저장될 것이다.
그 후 'D -1'이 입력되면 min_heap에서 (3, 0)이 삭제되며 exist[0] = 0이 된다.
max_heap에서는 (3, 0)이 당장 삭제되진 않겠지만, 후에 exist[0]을 검사하면서 (3, 0)을 출력하지는 않을 것이다.

위 코드는 중복된 값들도 모두 삽입한다는 단점이 있다.
아래 코드는 딕셔너리를 활용해 중복된 값을 삽입하지 않게 구현한 것이다.

2. 딕셔너리로 삽입 여부 확인

import sys
import collections
import heapq

input = sys.stdin.readline

for _ in range(int(input())):
    min_heap = []
    max_heap = []
    exist = collections.defaultdict(int)

    def clear(heap, k=1):
        while heap and not exist[heap[0] * k]:
            heapq.heappop(heap)

    """ execute the commands """
    for _ in range(int(input())):
        command = input().split()
        # I n
        if command[0] == 'I':
            n = int(command[1])
            if not exist[n]:
                heapq.heappush(min_heap, n)
                heapq.heappush(max_heap, -n)
            exist[n] += 1
        # D -1
        elif command[1] == '-1':
            clear(min_heap)
            if not min_heap:
                continue
            exist[min_heap[0]] -= 1
            if not exist[min_heap[0]]:
                heapq.heappop(min_heap)
        # D 1
        else:
            clear(max_heap, -1)
            if not max_heap:
                continue
            exist[-max_heap[0]] -= 1
            if not exist[-max_heap[0]]:
                heapq.heappop(max_heap)

    clear(min_heap)
    clear(max_heap, -1)

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

중복되는 값의 삽입/삭제가 생략되어 훨씬 빠른 속도로 실행되었다.
1번 코드는 3328ms, 2번 코드는 2692ms로 AC를 받았다.

참고로 collections.deque를 활용하는 방법은 부적절하다.
삭제는 O(1)에 구현할 수 있더라도, bisect.insort 함수를 사용할 시 삽입에는 O(N)이 소요된다.