문제

풀이

모르겠어서 풀이 봄.
1. 한개의 heap으로는 해결이 나지 않으므로 최대 / 최소 heap을 따로 선언해서 사용함.
2. check란 확인용 배열을 만든 후, heap에 push할 때 index값을 같이 넣어면서 check[index]를 True로 변경 함.
3. heappop연산을 수행할 때, check[idx] = False로 바꿔주면 다른 곳 연산을 막아줌.
(그러므로 heappop하기 전에, check가 False인 값들을 전부 꺼내줘야 함.)
4. 마지막에 불필요한 연산 값들을 전부 제거 후 결과 값 출력

코드

import heapq
import sys

def solution() :
    t = int(sys.stdin.readline())
    
    for _ in range(t) :
        k = int(sys.stdin.readline())
        max_heap = []
        min_heap = []
        check = [False] * k
        
        for i in range(k) :
            o, n = sys.stdin.readline().split()
            
            if o == 'I' :
                heapq.heappush(min_heap, (int(n), i))
                heapq.heappush(max_heap, (-int(n), i))
                check[i] = True
            elif n == '-1' :
                if n == '-1' :
                    while min_heap and not check[min_heap[0][1]] :
                        heapq.heappop(min_heap)
                    if min_heap :
                        check[min_heap[0][1]] = False
                        heapq.heappop(min_heap)
            else :
                while max_heap and not check[max_heap[0][1]] :
                    heapq.heappop(max_heap)
                if max_heap :
                    check[max_heap[0][1]] = False
                    heapq.heappop(max_heap)
    
        while min_heap and not check[min_heap[0][1]] :
            heapq.heappop(min_heap)
        while max_heap and not check[max_heap[0][1]] :
            heapq.heappop(max_heap)
        
        if max_heap and min_heap :
            print(f'{-max_heap[0][0]} {min_heap[0][0]}')
        else :
            print('EMPTY')

solution()