[BOJ] 7662 이중 우선순위 큐

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

처음에는 heapq 하나 만들어서 최대값 출력이면 리스트 전체에 -를 곱해서 뽑고 다시 -곱해서 원래대로 돌려주고 이렇게 할까 생각했는데 리스트 최대 개수가 거의 백만이라서 시간초과가 날 것 같아서 일단 버렸다. 도저히 생각이 안 나서 강의를 들었다.

강의에서 제안한 방식

heapq를 두 개 만들어서 각각 최대힙과 최소힙으로 두고 두 힙을 동기화 시키라고 했다. 동기화를 위해서 값과 들어온 순서를 튜플로 만들어서 힙에 넣고, 들어온 순서를 key로 하는 해시테이블(이라하고 그냥 [False] * 백만)을 두고 값이 나갈 때 True로 변환해서 다른 힙에서 해당 값이 나오면 그냥 한 번 더 뽑게하는 방식을 사용했다. 일단 이거만 보고 코드를 만들어봤다.

내 코드

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

for _ in range(int(input())):
  i=0
  maxheap = []
  minheap = []
  c = int(input())
  removed = [0] * c
  for _ in range(c):
    op, num = input().split()
    num = int(num)
    if op == 'I':
      heappush(minheap, (num, i))
      heappush(maxheap, (-num, i))
      i+=1
    elif op == 'D' and num == 1:
      if len(maxheap):
        x, idx = heappop(maxheap)
        while len(maxheap) and removed[idx]:
          x, idx = heappop(maxheap)

        removed[idx] = 1
    else:
      if len(minheap):
        x, idx = heappop(minheap)

        while len(minheap) and removed[idx]:
          x, idx = heappop(minheap)
        removed[idx] = 1

  if len(maxheap) and len(minheap):
    print(heappop(maxheap)[0] * -1, heappop(minheap)[0])
  else:
    print('EMPTY')

제일 처음에는 removed 리스트를 0으로 초기화 안 하고 나갈 때마다 append로 removed리스트에 값을 추가해주고 나중에 비교할 때 x in removed 를 통해서 확인을 했다. 그랬더니 시간초과가 나서 0으로 초기화한 배열로 바꿨다. 그런데 틀렸다고 나왔다.
정답코드랑 논리는 비슷하게 작성했고 chat GPT도 같은 코드라고 말해줬는데 내 코드만 틀리다.
질문하기에서 테스트 케이스를 찾아서 돌려봤는데

1
5
I 1
I 3
D 1
D 1
I 2

여기서 2, 2가 나와야하는데 내 코드는 2, 1이 나온다. 내 코드에서는 한 쪽에서만 나가는 연산이 있으면 다른 쪽에서 pop이 생기기 전까지 반영을 안 해줬다. 보니까 맨 마지막 pop 연산에서 정답코드는 pop을 따로 함수로 만들어서 관리해서 removed에 있는 것을 걸러줬는데 나는 그냥 heappop이다보니까 그 과정이 없었다.

고친 코드

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

for _ in range(int(input())):
  i=0
  maxheap = []
  minheap = []
  c = int(input())
  removed = [0] * c
  for _ in range(c):
    op, num = input().split()
    num = int(num)
    if op == 'I':
      heappush(minheap, (num, i))
      heappush(maxheap, (-num, i))
      i+=1
    elif op == 'D' and num == 1:
      if len(maxheap):
        x, idx = heappop(maxheap)
        while removed[idx] and len(maxheap):
          x, idx = heappop(maxheap)
        removed[idx] = 1
    else:
      if len(minheap):
        x, idx = heappop(minheap)
        while removed[idx] and len(minheap):
          x, idx = heappop(minheap)
        removed[idx] = 1

  if len(maxheap) and len(minheap):
    max, idx = heappop(maxheap)
    while removed[idx] and len(maxheap):
      max, idx = heappop(maxheap)

    min, idx = heappop(minheap)
    while removed[idx] and len(minheap):
      min, idx = heappop(minheap)

    print(-max, min)

  else:
    print('EMPTY')

그런데도 22%에서 틀렸다고 나오는데 왜인지 모르겠다 도저히