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

문제 링크

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

7662번: 이중 우선순위 큐

풀이 

- heapq을 사용해서 풀었는데 시간초과가 발생하였다. 

- 파이썬 힙의 경우 popleft()은 실행이 불가능하고 최소힙만 지원하기 때문에 

I 명령일 경우 최소힙에 숫자를 삽입하였다. 

D -1 일 경우, 최소힙에서 Pop 명령어를 통해 최솟값을 제거하였다.

D 1 일경우, 최소힙에서 heapq.nlargest(1, heap) 명령어를 통해 가장 큰 값 1개를 불러오고 이 후 remove 명령어를 통해 힙에서 제거해줬다. 

+ heapq.nlargest(n, heap) : heap에서 가장 큰 값 n개를 담고 있는 리스트 반환 

import heapq
import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
  n = int(input())
  
  heap = []
  
  for i in range(n):
    s = input().split()

    if s[0] == 'I':
      heapq.heappush(heap,int(s[1]))
      
    if s[0] == 'D':
      if heap :
        # 최솟값 삭제 
        if s[1] == '-1':
             heapq.heappop(heap)
        else :
        # 최댓값 반환 후 삭제 
            num = heapq.nlargest(1, heap)[0]
            heap.remove(num)

  if heap:
    print(max(heap), min(heap))
  else:
    print('EMPTY')

- 최소힙, 최대힙 두개의 큐로 구현해보았다. 두 개의 힙을 동기화 하는 부분은 다른 블로그를 참고 했다 ㅠㅠ 

파이썬에서 최대힙은 부호를 변경하여 대입해주면 된다. 

exist[id] : 인덱스는 입력된 숫자의 고유 번호이다. 

- 숫자를 삽입할 땐 exist[id]를 True로 변경한다.

- 숫자를 삭제할 땐 

최소힙과 최대힙의 숫자들을 동기화 시켜줘야 하기 때문에 exist[id]가 False인데 큐에 존재한다면 pop()을 통해 제거해준다. 

D -1 일 경우 최소힙이 비어있지 않으면 최솟값을 제거한다.

D 1 일 경우 최대힙이 비어있지 않으면 최댓값을 제거한다. 

- 마지막 출력 전에도 동기화를 시켜주고 힙에 숫자가 남아있다면 최댓값과 최솟값을 출력한다.

최댓값의 경우 max_heap에 마이너스 부호를 붙여주고 삽입했기 때문에 마이너스 부호를 붙여 출력한다. 

- 어렵다 ..

import heapq
import sys
input = sys.stdin.readline

# 동기화 
def sync(h):
  while h and not exist[h[0][1]]:
    heapq.heappop(h)
    
t = int(input())

for _ in range(t):
  n = int(input())
  
  max_heap = []
  min_heap = []
  # 인덱스는 입력된 숫자의 고유 번호 
  exist = [False] * 1000001
  
  for i in range(n):
    s, num = input().split()
    num = int(num)
    
    if s== 'I':
      heapq.heappush(max_heap, (-int(num), i))
      heapq.heappush(min_heap, (int(num), i))
      # 존재함을 표시 
      exist[i] = True
      
    if s == 'D':
      if num == -1 :
        sync(min_heap)
        
        if min_heap:
          exist[min_heap[0][1]] = False
          heapq.heappop(min_heap)
      else :
        sync(max_heap)
        
        if max_heap :
          exist[max_heap[0][1]] = False
          heapq.heappop(max_heap)

  sync(max_heap)
  sync(min_heap)
  
  if max_heap and min_heap:
    print(-max_heap[0][0], min_heap[0][0])
  else:
    print('EMPTY')