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

문제

이중 우선순위 큐

7662번: 이중 우선순위 큐

 

풀이

우선순위 큐, 즉 heap 자료구조는 일반적으로 '최소 힙'과 '최대 힙'으로 구성된다.

 

이에 대한 추가적인 설명은 자료구조 - 힙 을 참고하길 바란다.

 

하지만, 해당 문제에서는 최대, 최소에 대한 두개의 우선순위를 가지는 큐를 구성해 연산을 진행해야 한다.

 

그렇기 떄문에 일반적인 방법으로 heap을 생성해서는 문제를 제한시간 내에 해결할 수 없다.

 

일반적으로 드는 생각은 최대 힙, 최소 힙을 둘다 생성해

• 'D 1'일 경우에는 최대 힙에서 추출
• 'D -1'일 경우에는 최소 힙에서 추출

하는 방법이 떠오를 것이다.

 

이런 방법을 사용하는 경우에, 최대 힙과 최소 힙의 정보가 불일치하는 경우가 생기기 때문에, 두 힙의 원소에 대해 동기화 시켜주는 작업이 꼭 필요하다.

 

예를 들어,
I 1
I 2
I 3
D 1
의 연산이 있다고 하면,

 

max_heap = [3,2,1], min_heap = [1,2,3]이 될것이고 D 1의 연산을 하게 되면 max_heap = [2,1], min_heap = [1,2,3]으로 두개 힙의 원소가 다르기 때문에 제대로 된 정답을 출력할 수 없다.

 

동기화를 시켜주는 방법에는 여러가지가 있겠지만, 시간과 메모리 제한 내에 연산을 마쳐야 하므로 가장 효율적인 방법을 찾아야 한다.

일례로, pop연산을 마친 heap을 기준으로 그 반대 우선순위의 힙을 생성해주면 동기화를 마칠 수 있지만, 그 과정에서 heap 정렬 연산이 필요하므로 시간 비효율적이다.

 

그러므로, 동기화를 위해 외부에 두 heap의 원소에 대한 정보를 기록해 두는 dictionary를 생성해 이를 기반으로 동기화 작업을 하는 알고리즘을 생각해볼 수 있다.

• 알고리즘 진행 방식
  • I 연산
    1. 최소 힙, 최대 힙에 정수를 각각 추가하고 dictionary에 해당 정수의 key값이 이미 존재하면 value+1, 그렇지 않으면 1로 초기화

if command=='I':
	heapq.heappush(max_heap, -int(num))
	heapq.heappush(min_heap, int(num))
	if int(num) in dic.keys():
		dic[int(num)]+=1 
	else: 
		dic[int(num)]=1

• D 연산
  • D 1
    1. 최대 힙의 원소가 있는지 확인. 없으면 무시
    2. 최대 힙의 첫번째 값(최대값)을 key로한 dictionary의 value가 0일 경우, 즉, 두 힙 모두에 해당 정수가 없어야 하는 경우에 삭제
    3. 최대값에 대한 dictionary value가 1 이상일 때까지 반복
    4. 최대값 pop & 최대값에 대한 dictionary value -1
  • D -1
    • D 1과 같은 메커니즘으로 작동

• else:
      if int(num)==1:
          while True:
              if max_heap:
                  if dic[-max_heap[0]]==0:
                      heapq.heappop(max_heap)
                  else: 
                      break
              else:
                  break
          if max_heap:
              dic[-heapq.heappop(max_heap)]-=1
  
      else:
          while True:
              if min_heap:
                  if dic[min_heap[0]]==0:
                      heapq.heappop(min_heap)
                  else: 
                      break
              else:
                  break
          if min_heap:
              dic[heapq.heappop(min_heap)]-=1

  • 최종 동기화 후, 출력

    while True:
        if max_heap:
            if dic[-max_heap[0]]==0:
                        heapq.heappop(max_heap)
            else: 
                break
        else:
            break
    while True:
    if min_heap:
        if dic[min_heap[0]]==0:
            heapq.heappop(min_heap)
        else: 
            break
    else:
        break

• 전체 코드

# 이중 우선순위 큐
import sys, heapq
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
    k = int(input().strip())
    max_heap, min_heap = [],[]
    dic = {}
    for _ in range(k):
        command, num = input().strip().split()
        if command=='I':
            heapq.heappush(max_heap, -int(num))
            heapq.heappush(min_heap, int(num))
            if int(num) in dic.keys():
                dic[int(num)]+=1
            else:
                dic[int(num)]=1
        else:
            if int(num)==1:
                while True:
                    if max_heap:
                        if dic[-max_heap[0]]==0:
                            heapq.heappop(max_heap)
                        else: 
                            break
                    else:
                        break
                if max_heap:
                    dic[-heapq.heappop(max_heap)]-=1

            else:
                while True:
                    if min_heap:
                        if dic[min_heap[0]]==0:
                            heapq.heappop(min_heap)
                        else: 
                            break
                    else:
                        break
                if min_heap:
                    dic[heapq.heappop(min_heap)]-=1
    # 마지막 동기화    
    while True:
            if max_heap:
                if dic[-max_heap[0]]==0:
                            heapq.heappop(max_heap)
                else: 
                    break
            else:
                break
    while True:
        if min_heap:
            if dic[min_heap[0]]==0:
                heapq.heappop(min_heap)
            else: 
                break
        else:
            break

    if min_heap:
        _max = -heapq.heappop(max_heap)
        _min = heapq.heappop(min_heap)
        print(_max, _min)
    else:
        print('EMPTY')