접근 방법

1. heapq를 통해 우선순위큐를 구현해서 집어넣는다.
2. D -1일 경우 최소힙으로 구현된 큐에서 값을 갖고온다.
3. D 1일 경우 list에서 바로 최댓값을 제거한다.

이렇게 풀었더니 시간초과가 발생했다.
아마 최대값을 제거하는 과정에서 시간이 오래걸리지 않았을까 생각한다.

조금 찾아보다 최대힙과 최소힙을 둘다 구현해서 동기화시켜서 해결하는 방법을 참고해서 구현하기로 했다.

1. heapq를 통해 최대힙과, 최소힙에 값을 집어넣는다.
2. 입력한 값을 dict로 따로 관리해준다.
3. D 1 일 경우 최대힙의 값을 제거하고 dict에서 해당 값의 value를 0으로 만든다.
4. D -1 일 경우 최소힙의 값을 제거하고 dict에서 해당 값의 value를 0으로 만든다.
5. 만약 원소의 개수가 0보다 작거나 같다면 empty를 출력하고
6. 값이 존재한다면 최대힙과 최소힙을 동기화하여 최대값과 최소값을 출력해준다.

import heapq
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().rstrip()


t = int(input())
for _ in range(t):
    k = int(input())
    min_heap = []
    max_heap = []
    total_ele_cnt = 0
    ele_cnt = defaultdict(int)

    for _ in range(k):
        operator, num = input().split()
        num = int(num)

        if operator == "I":
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap, -num)
            total_ele_cnt += 1
            ele_cnt[num] += 1

        elif operator == "D":
            if total_ele_cnt <= 0:
                continue
            if num == 1:
                while True:
                    del_num = -heapq.heappop(max_heap)
                    if ele_cnt[del_num] != 0:
                        ele_cnt[del_num] -= 1
                        break
            elif num == -1:
                while True:
                    del_num = heapq.heappop(min_heap)
                    if ele_cnt[del_num] != 0:
                        ele_cnt[del_num] -= 1
                        break
            total_ele_cnt -= 1

    if total_ele_cnt <= 0:
        print("EMPTY")
    else:
        while True:
            max_v = -heapq.heappop(max_heap)
            if ele_cnt[max_v] != 0:
                break
        while True:
            min_v = heapq.heappop(min_heap)
            if ele_cnt[min_v] != 0:
                break
        print(max_v, min_v)