문제 설명

이번 포스팅은 백준 7662번: 이중 우선순위 큐 문제 풀이에 대한 기록입니다.

[ 입출력 ]

문제를 간단히 요약하자면, "정수를 저장하는 이중우선 큐가 있을 때, 1) 값 삽입, 2) 최댓값 삭제, 3) 최솟값 삭제, 세 가지로 구성된 일련의 연산을 마친 후 큐에 남아있는 최댓값과 최솟값을 출력하는 문제" 입니다.

풀이

1. 최소 힙, 최대 힙으로 우선순위 큐를 각각 따로 두기 (heapq 이용)

---

이 문제의 관건은 최댓값, 최솟값을 빠르게 찾아 제거하는 것입니다.

보통 이런 작업을 위해선 우선순위 큐를 사용하지만, 이 문제에서는 특이하게

1) 값이 작을수록 높은 우선순위를 가짐
2) 값이 클수록 높은 우선순위를 가짐

두 가지의 우선순위가 필요합니다.

이를 하나의 우선순위 큐를 사용해서 구현하는 것은 어려움이 있으므로,

값이 작을수록 높은 우선순위를 가지는 최소 힙과
값이 클수록 높은 우선순위를 가지는 최대 힙을 이용하여

두 개의 우선순위 큐를 따로 두고 운영하는 방법을 사용해야 합니다.

파이썬의 heapq 모듈은, 이진트리 기반의 최소 힙 자료구조를 제공합니다.

아래 예시와 같이 heapq를 이용하여 손쉽게 최소 힙, 최대 힙을 구현할 수 있습니다.

import heapq

min_heap = []
max_heap = []

num = 8

# min_heap에 추가
heapq.heappush(min_heap, num)
# max_heap에 추가
heapq.heappush(max_heap, -num)

heapq는 기본적으로 최소 힙, 즉 값이 작을수록 높은 우선순위를 가집니다.

따라서 최대 힙을 구현하기 위해선, 값을 추가할 때 '$-$'를 붙여 부호를 바꾸어 추가하고, 추출할 때 다시 원래대로 되돌려 주는 방식으로 사용해야 합니다.

이 방법을 활용하여 값의 삽입(I) 연산까지만 구현한 모습은 아래와 같습니다.

우선 빨간 박스로 표시된 부분에 주목해서 보시면 됩니다!

nums 변수와 중복 삽입 / 최초 삽입으로 분기를 나눈 것에 대해서는 아래에서 이어서 설명하겠습니다.

2. 각자 존재하는 두 힙의 정보를 동기화

---

최소 힙과 최대 힙을 각각 따로 두어 운영하면 최솟값과 최댓값을 바로바로 찾을 수 있어 빠른 연산이 가능할 것입니다. 여기까진 좋습니다.

그러나 이로 인해 한 가지 문제가 생깁니다.

"어느 한 쪽 힙에서 값을 제거하면, 다른 한 쪽에는 반영되지 않는 것" 입니다.

"D 1" 연산을 처리하여 최대 힙에서 최댓값을 제거해도, 최소 힙에선 그 값이 제거되지 않고 남아있게 됩니다.

"D -1" 연산을 처리했을 때도 마찬가지입니다.

이로 인해, 다음 연산에서 이미 삭제된 값을 다시 삭제하는 등의 경우가 발생한다면 잘못된 결과를 만들어낼 수 있습니다.

따라서, 한 쪽 힙에서만 값이 제거되더라도 다른 한 쪽에서 알 수 있도록 "값의 추가, 삭제를 공통적으로 기록하고 공유하는 공간" 을 두어야 합니다.

이 공유 공간이 바로 위에서 나왔던 "nums" 입니다.

nums = dict()

저는 이 nums를 데이터 탐색과 제거가 $O(1)$인 dictionary 자료구조를 사용하였습니다.

2-1. 값을 추가하는 경우

import sys
import heapq

t = int(sys.stdin.readline())

for i in range(t):
    min_heap = []
    max_heap = []
    nums = dict()	# 값의 추가, 삭제를 공통적으로 기록하고 공유하는 공간
    k = int(sys.stdin.readline())
    
    for j in range(k):
        oprt, oprd = sys.stdin.readline().split()
        num = int(oprd)
        
        if oprt == 'I':
            # 중복 삽입일 때
            if num in nums:
                nums[num] += 1
            # 최초 삽입일 때
            else:
                nums[num] = 1
                # min_heap에 추가
                heapq.heappush(min_heap, num)
                # max_heap에 추가
                heapq.heappush(max_heap, -num)

최초 삽입일 때는, nums[num] = 1 을 하여 새로운 값을 nums에 추가해줌과 동시에 그 값(개수)를 1로 저장하여 값이 추가 되었음을 저장합니다.

중복 삽입일 때는, nums[num] += 1 을 하여 개수만 +1 해주는 방식으로 추가되었음을 반영합니다.

2-2. 값을 삭제하는 경우

elif oprt == 'D':
    # 큐가 비어있지 않을 때만
    if not isEmpty(nums.items()):
        # 최댓값을 제거
        if num == 1:
            while -max_heap[0] not in nums or nums[-max_heap[0]] < 1:
                temp = -heapq.heappop(max_heap)
                if temp in nums:
                    del(nums[temp])
            nums[-max_heap[0]] -= 1
        # 최솟값을 제거
        else:
            while min_heap[0] not in nums or nums[min_heap[0]] < 1:
                temp = heapq.heappop(min_heap)
                if temp in nums:
                    del(nums[temp])
            nums[min_heap[0]] -= 1

값의 삭제는 큐가 비어있지 않을 때만 가능하므로, 이를 체크해야 합니다.

아래가 isEmpty() 함수의 내부입니다.

# 삭제할 데이터가 있는지 체크하는 함수
def isEmpty(nums):
	# nums에 1인 데이터가 하나라도 있으면 비어있지 않은 것
    for item in nums:
        if item[1] > 0:
            return False
    return True

큐가 비어있지 않다면, 삭제 연산을 진행합니다.

최댓값을 제거하는 경우, 우선 현재 최대 힙의 head에 있는 데이터가 "허수(삭제되었지만 반영이 되지 않아 남아있는 데이터") 인지 확인해야 합니다.

만약 head에 있는 데이터가 nums에 존재하지 않거나 nums에 값이 0인 상태로 존재한다면, 이 데이터는 실제로는 삭제되었지만 아직 남아있는 데이터입니다.

따라서 힙에서 제거합니다. 또한 그 데이터가 아직 nums에 남아있다면 del(nums[temp]) 하여 nums에서도 삭제해줍니다.

nums[num]의 값이 0인 상태라면 이미 '삭제된 데이터'라는 의미인데도, 굳이 nums에서까지 삭제하도록 구현한 이유는 아래와 같은 경우가 발생했기 때문입니다.

input >
I 2
D 1
I 2

I 2 $\to$ min_heap = [2], max_heap = [-2], nums = [2 : 1]
D 1 $\to$ min_heap = [2], max_heap = [], nums = [2 : 0]
I 2 $\to$ min_heap = [2], max_heap = [], nums = [2 : 1]


※ 2는 삭제되었다가 다시 추가되었지만, nums에는 남아있었기 때문에 max_heap에 새로 추가되지 않는 상황이 발생

※ 중복 삽입 조건을 if num in nums and nums[num] > 0: 로 변경하여 max_heap에 2가 추가되게 할 수 있지만, min_heap에도 추가되어 min_heap = [2, 2]가 되는 상황이 발생

3. 결과 출력하기

---

연산을 모두 성공적으로 처리했다면, 결과를 출력하는 것은 간단합니다.

# 결과 출력           
if isEmpty(nums.items()):
	print('EMPTY')
else:
	while min_heap[0] not in nums or nums[min_heap[0]] < 1:
		heapq.heappop(min_heap)
	while -max_heap[0] not in nums or nums[-max_heap[0]] < 1:
 		heapq.heappop(max_heap)
print(-max_heap[0], min_heap[0])

isEmpty()로 비어있는 지를 체크하여 비어있다면 'EMPTY'를 출력합니다.

그렇지 않으면, 최소 힙과 최대 힙에서 각각 허수(삭제되었지만 남아있는 데이터)를 제거한 뒤 head의 데이터를 출력하면 각각이 최솟값, 최댓값이 되게 됩니다.

문제 해결!!

결과 코드

import sys
import heapq

def isEmpty(nums):
    for item in nums:
        if item[1] > 0:
            return False
    return True

t = int(sys.stdin.readline())

for i in range(t):
    min_heap = []
    max_heap = []
    nums = dict()
    k = int(sys.stdin.readline())
    
    for j in range(k):
        oprt, oprd = sys.stdin.readline().split()
        num = int(oprd)
        
        if oprt == 'I':
            # 중복 삽입일 때
            if num in nums:
                nums[num] += 1
            # 처음 삽입일 때
            else:
                nums[num] = 1
                # min_heap에 추가
                heapq.heappush(min_heap, num)
                # max_heap에 추가
                heapq.heappush(max_heap, -num)
                
        elif oprt == 'D':
            # 큐가 비어있지 않을 때만
            if not isEmpty(nums.items()):
                # 최댓값을 제거
                if num == 1:
                    while -max_heap[0] not in nums or nums[-max_heap[0]] < 1:
                        temp = -heapq.heappop(max_heap)
                        if temp in nums:
                            del(nums[temp])
                    nums[-max_heap[0]] -= 1
                # 최솟값을 제거
                else:
                    while min_heap[0] not in nums or nums[min_heap[0]] < 1:
                        temp = heapq.heappop(min_heap)
                        if temp in nums:
                            del(nums[temp])
                    nums[min_heap[0]] -= 1
     
    # 결과 출력           
    if isEmpty(nums.items()):
        print('EMPTY')
    else:
        while min_heap[0] not in nums or nums[min_heap[0]] < 1:
            heapq.heappop(min_heap)
        while -max_heap[0] not in nums or nums[-max_heap[0]] < 1:
            heapq.heappop(max_heap)
        print(-max_heap[0], min_heap[0])