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

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

7662번: 이중 우선순위 큐

사람마다 느끼는 난이도는 다르겠지만, 나한텐 개어려웠다.

처음에 min_heap과 max_heap을 다 만들어놓고 한쪽에서 삭제된걸 어떻게 삭제할까 하다가 그냥 remove()써서 삭제했더니 당연히 시간초과... 이 remove함수를 대체하여 다른것을 생각해내는데 시간이 매우 오래결렸다.

(2틀동안 이것만 붙잡고 있었음)

max_heap을 구현하는데 (-num,num) 의 튜플형태로 구현하여 문제를 풀었던 기억이 나, 튜플형태로 heappush를 하여 제거해야할 숫자를 기억하게 했다.

글로만으로는 이해하기가 어렵기 때문에 코드는 다음과 같다.

 

import sys
import heapq
def Sol():
  input = sys.stdin.readline
  T = int(input())
  for _ in range(T):
    min_heap = []
    max_heap = []
    k = int(input())
    check = [1] * k
    for i in range(k):
      cal, num = input().split()
      num = int(num)
      if cal == "I":
        heapq.heappush(min_heap,(num,i))
        heapq.heappush(max_heap,(-num,i))
      else:
      ## 원소를 제거함과 동시에 해당하는 숫자의 인덱스를 통해 check의 1을 0으로 삭제되었음을 표시.
        if num == -1:
          if min_heap:
            check[heapq.heappop(min_heap)[1]] = 0
        elif num == 1:
          if max_heap:
            check[heapq.heappop(max_heap)[1]] = 0
            
      ## 다음 제거 대상이 될 인덱스에 있는 원소가 이미 다른 쪽에서 지워진 원소면 제거
      while min_heap and check[min_heap[0][1]] == 0:
        heapq.heappop(min_heap)
      while max_heap and check[max_heap[0][1]] == 0:
        heapq.heappop(max_heap)
    
    if min_heap == []:
      print("EMPTY")
    else:
      print(-max_heap[0][0], min_heap[0][0])

if __name__ == "__main__":
  Sol()

 

처음에 k만큼의 [1] 리스트를 준비하고, 한쪽에서 제거된 원소가 있으면 그 원소에 해당하는 인덱스의 숫자를 0으로 바꾸어주었다.

그 원소에 해당하는 고유 숫자를 부여하기 위해 for문의 i를 숫자와 함께 튜플로 heappush하였다.

 

다 풀고나서 다른 사람들 후기를 보니 저렇게 숫자(num)에 특정숫자(i)를 넣어 표시하는 것을 id를 추가하는 거라고 한다.

그리고 우선순위큐를 이용하여 문제를 해결하였지만, 다른 방법(map)으로 풀 수 있다고 한다.

난이도는 map으로 풀면 골드5, 우선순위큐로 풀면 골드2 이상 될거라고 하는 사람이 많았다.

(비슷한 문제로 1655번이 있는다는데, 둘다 푼 사람 중 일부는 1655번 보다 이 문제가 더 어렵다고 하였다)

하여간 나에게는 어려운 문제였기 때문에 더 성장할 수 있는 계기가 되었다.

 

pypy3말고도 python3으로도 통과된다.