[프로그래머스] 이중우선순위큐(LV3 - Python)

프로그래머쓱

해당 글에서는 이중우선순위큐 문제를 Python을 이용해 풀이하고자 한다.

프로그래머스

 

🔷 문제 설명

 

🔷 문제 풀이

먼저 필자가 풀이한 방식보다 더 효율성이 좋은 알고리즘이 있을 수 있다.

나름은 이해하기 쉬운 코드라고 생각하여, 문제가 어려운 사람들을 위해 돕고자 글을 올린다.

 

해당 문제를 푸려면 min_heap과 max_heap에 대해 알아야 한다.

• min-heap: 부모노드 값이 자식노드의 값보다 작다.
• max-heap: 부모노드 값이 자식노드의 값보다 크다.

즉, 큐에 삽입된 숫자들 중 최댓값, 최솟값을 구하기 위해서는 mix-heap, max-heap 모두 구현해야 한다.

하지만 파이썬에서 제공하는 힙(heapq)의 경우에는 최소 힙으로 구현되어 있으며, max-heap은 제공하지 않는다.

 

그렇다면 max-heap을 어떻게 파이썬의 heapq를 이용해 구현할 수 있을까?

 

바로 원래 값에 -1을 곱해 최댓값이 최소가 되도록 하는 것이다.

만약 1, 100이 삽입되고, 이를 -1을 곱해서 max-heap에 넣으면 [-100, -1]이 된다. 이때 heapq에서 heappop을 진행하게 되면, 가장 작은 값인 -100이 출력될 것이다. 여기서 다시 -1을 곱해주면, 원래의 값인 100이 최댓값으로 출력되는 것을 알 수 있다.

 

위 방법을 이용해 삽입(I) 연산을 구현한 코드가 다음과 같다.

min_heap = [] # 최솟값
max_heap = [] # 최댓값
for oper in operations:
    t, n = oper.split() # type/num
    n = int(n)

    if t=="I": # 삽입
        heapq.heappush(min_heap, n)
        heapq.heappush(max_heap, -n)

 

그렇다면, 삭제(D) 연산은 어떻게 해야할까?

여기서 중요한 점은, 동일한 원소가 min-heap, max-heap에 모두 들어있다는 것이다.

하지만 삭제 연산으로 인해 한 쪽에서 최댓값 혹은 최솟값이 삭제될 때, 다른 한 쪽에서는 삭제되지 않는다. 따라서 이를 처리해줘야 하며, 필자는 딕셔너리를 통해 해결하고자 했다.

 

처음 삽입할 때 넣은 숫자의 개수를 저장해두고, pop 연산이 일어날 때 해당 숫자의 개수를 다시 감소시키는 것이다. 만약에 숫자의 개수가 0이라면 이전 작업으로 인해 이미 삭제된 숫자에 해당하므로, 무시하고 다음 값을 삭제해줘야 한다.

 

이를 구현한 코드가 다음과 같다. num을 위주로 코드를 봐보면 이해가 쉬울 것이다.

min_heap = [] # 최솟값
max_heap = [] # 최댓값
num = {} # 숫자 개수 저장
for oper in operations:
    t, n = oper.split() # type/num
    n = int(n)

    if t=="I": # 삽입
        heapq.heappush(min_heap, n)
        heapq.heappush(max_heap, -n)
        if num.get(n): 
            num[n] += 1
        else: num[n] = 1
        
    else: # 삭제
        if n == 1: # 최댓값 삭제
            if len(max_heap):
                add = -heapq.heappop(max_heap)
            else: continue
            while max_heap and num[add] < 1:
                add = -heapq.heappop(max_heap)
            num[add] -= 1

        else: # 최솟값 삭제
            if len(min_heap):
                add = heapq.heappop(min_heap)
            else: continue
            while min_heap and num[add] < 1:
                add = heapq.heappop(min_heap)
            num[add] -= 1

 

이후 다른 코드는 요구 사항에 따라 구현해주면 된다. 해당 문제에서 중요한 점은 삭제될 때 heapq가 비어있는 경우에 예외 처리를 해줘야 된다는 점이다. 필자는 처음에 heapq가 비어있는 경우에 예외처리를 해줬지만, 실수로 continue가 아닌 break로 코드를 작성해 테스트케이스 2, 6에서 실패했었다.



1️⃣ Python 코드

위 풀이 방법을 기반으로 작성한 전체 코드는 아래와 같다.

import heapq
def solution(operations):
    answer = []
    
    min_heap = [] # 최솟값
    max_heap = [] # 최댓값
    num = {} # 숫자 개수 저장
    for oper in operations:
        t, n = oper.split() # type/num
        n = int(n)
        
        if t=="I": # 삽입
            heapq.heappush(min_heap, n)
            heapq.heappush(max_heap, -n)
            if num.get(n): 
                num[n] += 1
            else: num[n] = 1
            
        else: # 삭제
            if n == 1: # 최댓값 삭제
                if len(max_heap):
                    add = -heapq.heappop(max_heap)
                else: continue
                while max_heap and num[add] < 1:
                    add = -heapq.heappop(max_heap)
                num[add] -= 1
                
            else: # 최솟값 삭제
                if len(min_heap):
                    add = heapq.heappop(min_heap)
                else: continue
                while min_heap and num[add] < 1:
                    add = heapq.heappop(min_heap)
                num[add] -= 1
            
    while min_heap and num[min_heap[0]]<1:
        heapq.heappop(min_heap)
    min = min_heap[0] if len(min_heap) else 0
        
    while max_heap and num[-max_heap[0]]<1:
        heapq.heappop(max_heap)
    max = -max_heap[0] if len(max_heap) else 0
    
    return [max, min]