백준 - 이중 우선순위 큐(7662)

첫번째 시도

• 최소힙, 최대힙 두개를 운용하고, size만 조절해 D연산시 size 이상으로 pop을 못하게 하면 되지 않을까?

import heapq
T=int(input())
for _ in range(T):
  k = int(input())
  sQ = []
  lQ = []
  size=0
  for _ in range(k):
    cmd, num = input().strip().split()
    num = int(num)
    if(cmd=="I"):
      heapq.heappush(sQ,num)
      heapq.heappush(lQ,-num)
      size+=1
    if(size>0 and cmd=="D"):
      size-=1
      if(num==1):
        heapq.heappop(lQ)
      elif(num==-1):
        heapq.heappop(sQ)
  if(size==0):
    print("EMPTY")
  else:
    print(-lQ[0],sQ[0])

• 최대힙과 최소힙의 동기화가 제대로 되지 않아 아래와 같은 케이스에서 문제가 발생한다.

1
7
I 1
I 2
I 3
D 1
I 4
D -1
D -1

이후 시도들

• 동기화를 위해 size가 0이 되는 경우 최소힙, 최대힙 초기화 → 동기화 안됨 (틀렸습니다.)
• deque 하나만 운용하고, I는 그냥 append 한 후 ( O(1) ) D 연산시 sort 와 pop ( O(nlogn) ) → 시간 초과
• deque 두개를 운용(낮은 큐, 높은 큐). I 가 일어날 때 낮은큐에는 추가되는 숫자보다 낮은 숫자들이 순서대로 들어가고, 높은 큐에는 추가 숫자보다 높은 숫자들이 순서대로 들어가게 pop과 append를 통해 숫자를 이동 후 낮은 큐에 새로운 숫자 추가. ( O(n) ) . D 연산시 O(1) → 시간 초과
• 힙 두개 운영.(lQ, hQ). 동기화를 위해 반대편 큐에서 pop된 값을 찾아 float(’inf’)로 변경 → 잘 작동할 지도 미지수. O(n) 연산이기 때문에 시간초과

정답 보고 수정한 풀이

• 동기화를 꼭 제 때 할 필요는 없었다.
• 삭제해야할 값들을 따로 표시해놓고 pop 하면서 삭제’했어야 하는 값’인지 검사하고 버린다.
• 이 때 숫자를 직접 저장하면 범위상 필요한 메모리가 32GB가 넘어간다.
• 총 명령어 갯수인 k (백만 이하)를 노드 순서로 주면 용량도 절약하고 중복 숫자 처리도 쉬워진다. (대략 16MB)

import sys
import heapq
input = sys.stdin.readline
T = int(input())
ans=[]
for _ in range(T):
  k = int(input())
  lQ = []
  hQ = []
  deleted = [False]*k
  for i in range(k):
    cmd, num = input().strip().split()
    num = int(num)
    if(cmd == "I"):
      heapq.heappush(lQ, (num, i)) #최소힙
      heapq.heappush(hQ, (-num,i)) #최대힙
    if(cmd == "D"):
      if(num == 1):
        while hQ and deleted[hQ[0][1]]:
          heapq.heappop(hQ)
        if hQ:
          n, i = heapq.heappop(hQ)
          deleted[i] = True
      elif(num == -1):
        while lQ and deleted[lQ[0][1]]:
          heapq.heappop(lQ)
        if lQ:
          n, i = heapq.heappop(lQ)
          deleted[i] = True
  while lQ and deleted[lQ[0][1]]:
    heapq.heappop(lQ)
  while hQ and deleted[hQ[0][1]]:
    heapq.heappop(hQ)
  if(not lQ):
    ans.append("EMPTY")
  else:
    h = -hQ[0][0]
    l = lQ[0][0]
    ans.append(str(h) + " " + str(l))
  # print(lQ, hQ, deleted)
print(*ans,sep="\\n")