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

---

1. 코드

import heapq
import sys
from collections import defaultdict

ans = []
k = int(input())
for _ in range(k):
    n = int(input())
    d = defaultdict()
    min_h = []
    max_h = []
    idx = 0
    for _ in range(n):
        c, i = sys.stdin.readline().rstrip().split()
        i = int(i)
        if c == 'I':
            heapq.heappush(min_h, (i, idx))
            heapq.heappush(max_h, (-i, idx))
            d[idx] = [i, True]  # True: 아직 삭제되지 않은 상태
            idx += 1
        else:
            if i == 1:
                # 뽑은 값의 상태가 False: 이미 다른 힙에서 제거된 원소
                # 뽑은 값이 True 를 찾을 때까지 계속 값을 찾는다. while - if 순서 주의
                while max_h and not d[max_h[0][1]][1]:
                    heapq.heappop(max_h)
                # while 문을 거치고 나면 이 힙에서 뽑는 값은 True 상태 보장
                if max_h:
                    d[heapq.heappop(max_h)[1]][1] = False
            elif i == -1:
                while min_h and not d[min_h[0][1]][1]:
                    heapq.heappop(min_h)
                if min_h:
                    d[heapq.heappop(min_h)[1]][1] = False
    result = []
    for i in range(idx):
        if d[i][1]:
            result.append(d[i][0])
    if result:
        ans.append((max(result), min(result)))
    else:
        ans.append('EMPTY')

for i in ans:
    if i == 'EMPTY':
        print('EMPTY')
    else:
        print(i[0], i[1])

2. 후기

입력값을 힙에 넣을 때 해시값 역할을 해주는 변수인 idx를 사용했다. 같은 숫자가 힙 안에 있어도 idx 값이 서로 다르기 다른 값으로 식별할 수 있다.

d[idx]:
어떤 힙에서 뽑은 최대값 혹은 최소값이 이미 다른 힙에서 제거됐던 원소라면 d[idx] 값이 False 이다.

while - if:
while 문을 먼저 사용하여 뽑을 원소의 idx가 True가 나올 때 까지 pop()해준다. 만약 처음으로 뽑는 원소의 idx가 True인 경우라면 while문을 무시하고 바로 if문으로 건너가면 된다. pop()을 할 때는 while문을 사용하는 경우가 많은데, while-if 순서로 사용하는게 코드가 깔끔해진다.