Key

이중 Heap

1. OP1 삽입

   • 두 Heap에 동시에 넣고 현재 삽입 상태를 기억해두게 한다
   • vis[OP1 수행순서] = True

2. OP2 최소값 삭제

   • 이미 최대 heap으로 부터 삭제된 요소면 계속 pop
   • 최소 heap 남아 있는 값 있다면 현재 OP2를 수행 해야 하므로 pop
   • 삭제된 요소 표시 vis[OP2 수행순서] = False

3. OP3 최대값 삭제

   • 이미 최소 heap으로 부터 삭제된 요소면 계삭 pop
   • 최대 heap 요소가 남아 있다면 역시 OP3를 수행 하기 위해 pop
   • 삭제된 요소 표시 vis[OP3 수행순서] = False

이미 삭제된 요소 확인 방법이 vis[OP3 수행순서] = False 인것
삽입시 vis[OP1 수행순서] = True 해주기 때문에
힙에 들어간 요소는 삭제 되지 않는다면 무조건 True를 가리킬 것임

즉 pop을 진행하려 확인 하는데 이미 삭제된 요소임이 확인 되면
없는 요소 이므로 해당 힙에서도 제거를 해주고 실제 valid한 요소를 pop 해주는 로직

import heapq
T = int(input().strip())
for _ in range(T) :
  K = int(input())
  minQ =[]; maxQ = []
  vis = [False]*(K+1) 
  for i in range(K) :
    o, n = input().strip().split()
    if o == 'I' : 
      heapq.heappush(minQ, (int(n),i))
      heapq.heappush(maxQ, (-int(n),i))
      vis[i] =True
    else : 
      if n == '-1':
        while minQ and not vis[minQ[0][1]] : heapq.heappop(minQ)
        if minQ : 
          vis[minQ[0][1]] = False 
          heapq.heappop(minQ)
      else :
        while maxQ and not vis[maxQ[0][1]] : heapq.heappop(maxQ)
        if maxQ : 
          vis[maxQ[0][1]] = False 
          heapq.heappop(maxQ)

  while minQ and not vis[minQ[0][1]] : heapq.heappop(minQ)
  while maxQ and not vis[maxQ[0][1]] : heapq.heappop(maxQ)
  ans = [ -maxQ[0][0], minQ[0][0]] if maxQ and minQ else ['EMPTY'] 
  print(*ans)