⬛ [Programmers] [Python] [Level3] 이중 우선순위 큐

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

풀이

# 프로그래머스 3단계 - 이중 우선순위 큐
import heapq
def solution(operations):
    heap = []
    max_heap = []
    
    for o in operations:
        current = o.split()
        if current[0] == 'I':
            num = int(current[1])
            heapq.heappush(heap, num) # 최소 힙
            heapq.heappush(max_heap, (num*-1, num)) # 최대 힙
        else:
            if len(heap) == 0:
                pass
            elif current[1] == '1':
                max_value = heapq.heappop(max_heap)[1]
                heap.remove(max_value)
            elif current[1] == '-1':
                min_value = heapq.heappop(heap)
                max_heap.remove((min_value*-1, min_value))
    
    if heap:
        return [heapq.heappop(max_heap)[1], heapq.heappop(heap)]
    else:
        return [0,0]
print(solution(["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]))

이중 우선순위 큐 문제이다. 우선순위 큐는 힙 자료구조를 통해 구현이 가능하다. 

내가 쓴 방법은 기본적으로 힙 자료구조로 만드는 우선순위 큐는 최소 힙이므로 최대 힙을 따로 구현 하고

최소값을 빼야하면 최소힙에서 pop을 해주고 최대힙에서 remove를 해준다.

최대값을 빼야하면 최소힙에서 remove를 해주고 최대힙에서 pop을 해준다. 

 

문제를 풀다가 이렇게 구현하지 않고 heapq.nsmallest / heaqp.nlargest 라는 것이 있다는 것을 알았다. 

이걸 사용하면 굳이 최대/최소 힙을 구현하지 않아도 문제 해결이 가능하다. 

heap = heapq.nlargest(len(heap), heap)[1:]
heapq.heapify(heap)