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

2026.01.26ko 0 시리즈 · 알고리즘 #알고리즘

골드4 문제이며, 제한 시간은 6초이다.

문제

해결 과정

여러 방법을 시도해봤는데 역시 문제에 써있는대로 우선순위 큐를 사용했어야 한다. 처음엔 bisect를 사용해서 어디에 삽입할지 파악하는 방법을 생각했는데, 당연하게도 시간초과가 났다. 괜히 다르게 생각하다가 시간을 더 써버렸다 ㅠ

중요한 아이디어는 최소 힙과 최대 힙을 사용하며, 이 둘을 동기화 하는 작업이 중요하다. 나는 값에 식별자를 붙여서 동기화에 사용했다. tmp집합에 존재한다면 어디에서도 지워지지 않은 것이고, 존재하지 않으면 어디선가 지워졌다는 뜻이다.

풀이

import heapq

t = int(input())
for _ in range(t):
  k = int(input())
  min_heap = []
  max_heap = []
  tmp = set()
  id = 0
  for _ in range(k): 
    command, value = input().split()
    value = int(value)

    if command == 'I':
      heapq.heappush(min_heap, (value, id))
      heapq.heappush(max_heap, (-value, id))
      tmp.add(id)
      id += 1
    else:
      if not min_heap or not max_heap:
        continue
      
      if value == -1:
        while min_heap:
          v, i = heapq.heappop(min_heap)
          if i in tmp:
            tmp.remove(i)
            break
          
      elif value == 1:
        while max_heap:
          v, i = heapq.heappop(max_heap)
          if i in tmp:
            tmp.remove(i)
            break
  
  max_value = None
  while max_heap:
    max_value, i = heapq.heappop(max_heap)
    if i in tmp:
      break
    else:
      max_value = None
  if max_value is not None:
    tmp.remove(i)

  min_value = None
  while min_heap:
    min_value, i = heapq.heappop(min_heap)
    if i in tmp:
      break
    else:
      min_value = None
  if min_value is not None:
    tmp.remove(i)

  if max_value is None:
    print('EMPTY')
  else:
    max_value = -max_value
    if  min_value is None:
      min_value = max_value
    print(max_value, min_value)

아직 댓글이 없습니다.

문제

해결 과정

풀이

댓글

댓글 쓰기