[백준] 7662 이중 우선순위 큐

7662번: 이중 우선순위 큐

[백준/파이썬] 7662번 이중 우선순위 큐 풀이

개요

정수를 담은 자료구조를 다루는 문제입니다. 명령은 I 와 D 두가지로 주어집니다. 이 때 D 명령을 통해 가장 큰 값을 빼거나 가장 작은 값을 뺄 수 도 있습니다. 따라서 항상 적은 시간복잡도로 최대값, 최소값을 제거할 준비가 되있어야 합니다.

문제풀이

파이썬 라이브러리인 heapq를 이용해 최소힙 최대힙 자료구조 둘다 만들 수 있습니다. 이를 이용해 최소값, 최대값을 파악할 수 있습니다만, 유의해야할 점은 두 힙이 동기화되야 한다는 점입니다.

만약 최대값을 제거하라는 명령이 들어왔다면, 최대힙에서는 손쉽게 삭제할 수 있지만 최소힙에서 따라 지우려면 어떻게 해야할까요? list 내장메서드인 remove 를 사용하면 역시나 시간초과 판정을 받습니다. 이를 위해 값을 저장할때 식별할 수 있는 id를 함께 저장하고, 해당 id를 방문처리합니다.

...
  visited = [False] * (int(1e6)+1) 
  for i in range(int(input())):
    tmp = input().split()
    order, x = tmp[0], int(tmp[1])
    if order == 'I':
      heapq.heappush(minQ, (x, i))
      heapq.heappush(maxQ, (-x, i))
      visited[i] = True
...

값을 제거할때는 id가 이미 삭제됬는지 확인할 수 있게 visited를 업데이트 해줍니다. 만약 이미 삭제된 값이라면, 삭제되지 않은 값이 나올때까지 반복해서 삭제해줍니다.

...
  if x == 1:
    while maxQ and not visited[maxQ[0][1]]: heapq.heappop(maxQ)
    if maxQ:
      visited[maxQ[0][1]] = False
      heapq.heappop(maxQ)
  else:
    while minQ and not visited[minQ[0][1]]: heapq.heappop(minQ)
    if minQ:
      visited[minQ[0][1]] = False
      heapq.heappop(minQ)
...

정답코드

import sys
import heapq

def input():
  return sys.stdin.readline().rstrip()  

for _ in range(int(input())):
  minQ = []
  maxQ = []
  visited = [False] * (int(1e6)+1) 
  for i in range(int(input())):
    tmp = input().split()
    order, x = tmp[0], int(tmp[1])
    if order == 'I':
      heapq.heappush(minQ, (x, i))
      heapq.heappush(maxQ, (-x, i))
      visited[i] = True
    else:
      if x == 1:
        while maxQ and not visited[maxQ[0][1]]: heapq.heappop(maxQ)
        if maxQ:
          visited[maxQ[0][1]] = False
          heapq.heappop(maxQ)
      else:
        while minQ and not visited[minQ[0][1]]: heapq.heappop(minQ)
        if minQ:
          visited[minQ[0][1]] = False
          heapq.heappop(minQ)
  while maxQ and not visited[maxQ[0][1]]:heapq.heappop(maxQ)
  while minQ and not visited[minQ[0][1]]:heapq.heappop(minQ)
  if minQ and maxQ:
    print(-maxQ[0][0], minQ[0][0])
  else:
    print("EMPTY")

실패

remove 메서드를 활용한 방법. 시간초과로 실패했습니다.

import sys
import heapq

def input():
  return sys.stdin.readline().rstrip()  

for _ in range(int(input())):
  minQ = []
  maxQ = []
  for __ in range(int(input())):
    tmp = input().split()
    order, x = tmp[0], int(tmp[1])
    if order == 'I':
      heapq.heappush(minQ, x)
      heapq.heappush(maxQ, (-x, x))
    else:
      if len(minQ) == 0:
        continue
      if x == 1:
        minQ.remove(heapq.heappop(maxQ)[1])
      else:
        v = heapq.heappop(minQ)
        maxQ.remove((-v, v))
  if maxQ and minQ:
    print(maxQ[0][1], minQ[0])
  elif maxQ:
    print(maxQ[0][1], maxQ[0][1])
  elif minQ:
    print(minQ[0], minQ[0])
  else:
    print("EMPTY")