[백준BOJ] 7662번 이중 우선순위 큐.py

 

백준 저지에서 이중 우선순위 큐를 파이썬을 통해 풀어 보았다. 

 

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

7662번: 이중 우선순위 큐

7662번 이중 우선순위 큐.py

tomy9729/Algorithm

 

7662번 이중 우선순위 큐

 

문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 
정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. 
Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

 

설명

문제의 제목에서도 알 수 있듯이 두 개의 우선순위 큐를 활용해서 풀어야 하는 문제이다. 파이썬에서는 heapq라는 우선순위 큐를 제공하는데 heapq의 경우 최소 힙만을 지원한다. 최소 힙만 지원하는 heapq를 활용하여 최대 힙을 구현할 수 있다. 힙에 입력할 때 최대 힙의 경우 입력하는 값에 -1을 곱하여 입력함으로써 최대 힙과 같은 배열을 생성하며 출력할 때는 다시 -1을 곱하여 원하는 값을 얻을 수 있다.

 

최대 힙과 최소 힙 두 개의 힙을 활용한다. 둘 다 사용하는 이유는 두 가지다. 일단 시간 초과를 회피하기 위해 일반 큐 대신 힙을 사용한다. 다음으로 최댓값과 최솟값을 출력해야 하기 때문이다.

 

숫자가 입력되었을 때 최대 힙과 최소 힙에 전부 입력한다. 단 삭제 시가 문제인데 예를 들어 최대 힙에서 최댓값은 바로 삭제가 가능하지만 최솟값은 바로 삭제가 불가능하다. 이를 위해 최대 힙과 최소 힙이 가지고 있는 숫자에 대한 동기화가 필요하다. 즉 최대 힙에서 최댓값을 삭제할 때 이 숫자가 이미 삭제되었는지 아닌지 확인할 필요가 있다. 

 

만약 명령어로 "D 1"이 입력되어 최대 힙에서 최댓값을 삭제되어야 하는 상황이라고 가정한다. 최대 힙에서 최댓값을 삭제했지만 해당 값은 이미 최솟값에서 삭제된 값일 수도 있다. 이 경우 "D 1"에 대한 처리가 안 된 것이다. 이러한 상황을 막기 위해 동기화가 필요하다.

 

명령어 "I n"으로 인해 입력된 숫자 n들에 대해 n이 아직 큐에 존재하는지 삭제되었는지 판단이 필요하다. 이를 위해 visited라는 배열을 생성하며 0과 1로 삭제 여부를 구분한다. n이 입력된 index를 기준으로 삭제 여부를 visited에 기록하며 n의 index를 저장하기 위해 힙에 숫자를 저장할 때 튜플 형태로 index도 같이 저장한다. 여기서 index는 k값이다. 예를 들어 50이라는 숫자가 3번째로 입력되었다면 visited [2]=1이며 3번째로 입력된 숫자(50)가 삭제되면 visited [2]=0이다.

 

삭제를 진행한다. "D 1"이 입력되었다고 가정한다. 최대 힙에서 최댓값을 제거하되 해당 숫자가 이미 삭제되었는지를 visited를 통해 확인한다. 만약 이미 삭제되었다면 "삭제되지 않은 숫자들 중 최댓값"이 삭제되지 않았으므로 "삭제되지 않은 숫자들 중 최댓값"이 나올 때까지 계속 삭제를 진행한다. 최종적으로 최댓값을 삭제했으면 해당 값의 index를 통해 visited [index]=0으로 초기화한다. 이러한 과정은 "D -1"이 입력되었을 때도 마찬가지이다.

 

모든 명령어를 실행한 후에도 동기화가 진행되지 않아 "최대 힙(최소 힙)에서는 삭제되었으나 최소 힙(최대 힙)에서는 삭제되지 않은 숫자"가 존재할 수 있다. 마지막으로 동기화 과정을 한번 더 수행하고 최대 힙에서는 최댓값을, 최소 힙에서는 최솟값을 출력한다.

 

만약 이럼에도 시간초과가 발생한다면 "sys.stdin.readline"을 사용한다.

 

코드

#7662번 이중 우선순위 큐.py
import heapq
if __name__ == "__main__":
  t = int(input())
  for i in range(t) : 
    max_heap = []
    min_heap = []
    k = int(input())
    visited = [0]*k 
    for j in range(k) : 
      instruction = input()
      x = int(instruction[2:])
      if instruction[0] == "I" : 
        visited[j] = 1
        heapq.heappush(max_heap,(-x,j))
        heapq.heappush(min_heap,(x,j))
      elif x == 1 : 
        while len(max_heap) != 0 and visited[max_heap[0][1]] == 0 : #삭제한 숫자가 이미 삭제되어 있다면
          heapq.heappop(max_heap) # 다시 뽑기위해 제거
        if len(max_heap)!= 0 :
          visited[(heapq.heappop(max_heap))[1]] = 0 #숫자 삭제
      else : 
        while len(min_heap) != 0 and visited[min_heap[0][1]] == 0 :
          heapq.heappop(min_heap)
        if len(min_heap)!= 0 :
          visited[(heapq.heappop(min_heap))[1]] = 0
    
    while len(max_heap) != 0 and visited[max_heap[0][1]] == 0 :
      heapq.heappop(max_heap)
    while len(min_heap) != 0 and visited[min_heap[0][1]] == 0 :
      heapq.heappop(min_heap)
    if len(max_heap) != 0 and len(min_heap) != 0 : 
      print("%d %d"%(-max_heap[0][0], min_heap[0][0]))
    else : 
      print("EMPTY")