1. 문제 설명

이중 우선순위 큐

2. 문제 분석

삽입될 수를 담을 최대 힙과 최소 힙을 각각 구현한다. 최댓값을 삭제할 때에는 최대 힙에서, 최솟값을 삭제할 때에는 최소 힙에서 삭제한다. 이때 다른 힙에서 이미 삭제된 값이라면 힙에 수를 삽입할 때 체크한 명령어 별로 유니크한 인덱스 변수를 통해 유효한지 검사할 수 있다.

• 처음에는 heapq 모듈의 heapq.nlargest를 활용해 최댓값을 삭제할 때에는 최대 힙으로 만들고, 그 이후 heapq.heapify를 사용해 다시 최소 힙으로 만들면서 삽입과 삭제를 반복했지만, 시간 초과가 났다.

• 최소 힙과 최대 힙을 각각 구현할 때 중복된 수를 체크할 수 있다는 인사이트를 기억하고 있자.

3. 나의 풀이

import heapq
import sys

t = int(sys.stdin.readline().rstrip())
for i in range(t):
    k = int(sys.stdin.readline().rstrip())
    min_heap = []
    max_heap = []
    valid = [False for _ in range(1000001)]
    # cmd의 유니크한 인덱스로 이 명령어에 들어온 수가 유효한지 체크한다.
    for idx in range(k):
        cmd, num = sys.stdin.readline().rstrip().split()
        num = int(num)

        if cmd == 'I':
            heapq.heappush(min_heap, [num, idx])
            heapq.heappush(max_heap, [-1 * num, idx])
            valid[idx] = True
            # 이 idx에 들어온 num을 최대, 최소 힙 모두에 넣어준다.
            # 큐에 삽입했으므로 이 명령어는 현재 유효한 상태 True.
        else:
            # 유효한 값이 나올 때까지 팝하고, 삭제 가능하다면 삭제 후 이 인덱스는 더 이상 효과 X
            if num == 1:
                while max_heap and not valid[max_heap[0][1]]:
                    heapq.heappop(max_heap)
                if max_heap:
                    valid[heapq.heappop(max_heap)[1]] = False
            else:
                while min_heap and not valid[min_heap[0][1]]:
                    heapq.heappop(min_heap)

                if min_heap:
                    valid[heapq.heappop(min_heap)[1]] = False

    # 모든 삽입/삭제 끝난 이후 각 힙에서 유효한 값만 남기고 삭제한다.
    while max_heap and not valid[max_heap[0][1]]:
        heapq.heappop(max_heap)
    while min_heap and not valid[min_heap[0][1]]:
        heapq.heappop(min_heap)
    if not max_heap and not min_heap: print("EMPTY")
    else:
        # 각 최댓값, 최솟값을 힙에서 팝된 값을 통해 파악한다.
        max_num = heapq.heappop(max_heap)[0] * -1
        min_num = heapq.heappop(min_heap)[0]

        print(f"{max_num} {min_num}")