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

[Gold IV] 이중 우선순위 큐 - 7662 

[문제 링크](https://www.acmicpc.net/problem/7662)

🗝️알고리즘 분류

• 자료구조
• 우선순위 힙

---

💻문제 정의

큐에 데이터를 저장하는 연산과 데이터를 삭제하는 연산 두 가지가 존재한다. 삭제 연산에서, 큐의 데이터 중 최댓값을 삭제하는 연산과 최솟값을 삭제하는 연산 두 가지가 주어질 때, 모든 연산을 마친 후 큐에 남아있는 데이터의 최댓값과 최솟값을 출력하는 프로그램을 작성하는 것이 이번 문제이다.

 

💡접근 및 설계

우선 파이썬에서의 우선순위 큐는 최소 힙(Min heap)으로 구현된다. 최솟값을 제거하기 위해선 힙의 첫 번째 원소를 제거하면 된다. 하지만 최댓값을 제거하는 연산을 수행하기에는 최소 힙만으로는 구현이 힘들다. 따라서 최대 힙(Max heap)도 함께 구현한다.

 

파이썬에서 최대 힙을 구하기 위해선, 일반적인 큐에 원소를 추가할 때 -를 붙여 추가한다. 그러면 절댓값이 가장 큰 수가 가장 작은 수가 되므로 힙의 최상단에 위치하게 된다.

 

✏️알고리즘 풀이

T = int(input())

for _ in range(T):
    max_heap = [] # 최대 힙
    min_heap = [] # 최소 힙
    nums = {} # 힙의 값이 삭제될 때, 정보를 공유
    
    k = int(input())
    for _ in range(k):
        cmd, cmd2 = input().split()
        num = int(cmd2)

        # Insert
        if (cmd == "I"):
            if num in nums:
                nums[num] += 1
            else:
                nums[num] = 1
                heapq.heappush(min_heap, num) # 최소 힙에는 숫자 그대로
                heapq.heappush(max_heap, -num) # 최대 힙에는 숫자에 -를 붙혀서

우선 삽입 연산이다. 최대 힙과 최소 힙을 구현할 리스트를 생성한 다음, 입력받은 각 숫자를 각각의 힙에 넣는다.

 

# Delete
elif (cmd == "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

삭제 연산은 다음과 같다.

 

큐를 이중으로 사용하고 있기에, 삭제 연산이 요청되었을 때 한 쪽에서 삭제되면 다른 한 쪽에서도 삭제가 되어야 한다. 이를 nums 딕셔너리를 활용하여 해당 숫자의 등장 횟수를 가지고 판단할 수 있도록 구현하였다.

 

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

isEmpty 함수를 이용해 딕셔너리가 비어있는지 체크한다.

 

🗒️제출 코드

# 7662 이중 우선순위 큐

import heapq

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

T = int(input())

for _ in range(T):
    max_heap = [] # 최대 힙
    min_heap = [] # 최소 힙
    nums = {} # 힙의 값이 삭제될 때, 정보를 공유
    
    k = int(input())
    for _ in range(k):
        cmd, cmd2 = input().split()
        num = int(cmd2)

        # Insert
        if (cmd == "I"):
            if num in nums:
                nums[num] += 1
            else:
                nums[num] = 1
                heapq.heappush(min_heap, num) # 최소 힙에는 숫자 그대로
                heapq.heappush(max_heap, -num) # 최대 힙에는 숫자에 -를 붙혀서

        # Delete
        elif (cmd == "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])

---

💭오늘의 회고

약 한달만에 쓰는 글이다.

올해 목표가 하루 한 문제씩, 스트릭 깨지지 않고 연속 ~~~일 문제 풀이 였는데 백준 서버 문제로 스트릭이 깨지고 말았다.

약 100일 넘게 연속해서 문제를 풀었는데, 하루아침에 깨져버리니 뭔가 허탈감이랄까, 그동안의 족쇄가 풀린 느낌.

 

그래서 마음에 여유를 두고 오랜만에 코딩 문제를 풀어보았다. 역시나 아직 실력이 죽진 않은 것 같다.

 

올해 목표는 플래티넘. 이정도 페이스면 금방 달성할 것 같다. 아마 여름 끝날때 쯤이면 달성하지 않을까, 그때까지만이라도 열심히 해보자.