AlgorithmPrac4/BACKJOON7662.py at master · HYUN-SIUU/AlgorithmPrac4 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# 이중 우선순위 큐

import sys
import heapq
from collections import Counter

input = sys.stdin.readline

q = int(input())
result =[]
for _ in range(q):
    t = int(input())
    min_heap = []
    max_heap = []
    count = Counter()

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

        if cmd == 'I':
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap, -num)
            count[num] += 1
        elif cmd == 'D':
            if num == 1:
                while max_heap:
                    val = -heapq.heappop(max_heap)
                    if count[val] > 0:
                        count[val] -= 1
                        break
            elif num == -1:
                while min_heap:
                    val = heapq.heappop(min_heap)
                    if count[val] > 0:
                        count[val] -= 1
                        break

    while min_heap and count[min_heap[0]] == 0:
        heapq.heappop(min_heap)
    while max_heap and count[-max_heap[0]] == 0:
        heapq.heappop(max_heap)

    if not min_heap or not max_heap:
        result.append("EMPTY")
    else:
        result.append(str(-max_heap[0]) + " " + str(min_heap[0]))

print("\n".join(result))