[Python | 파이썬] 이중우선순위큐 (프로그래머스 HEAP)

[Python | 파이썬] 이중우선순위큐 (프로그래머스 HEAP)

 

 

이문제는 대놓고 우선순위큐를 이중으로 쓰라고 말해주고 있다.

따라서 최소힙과 최대힙을 두개 구현하여 푸는 단순한 방법이 있고, heapq 라이브러리의 다른 함수를 써서 푸는 방법이 있다.

주의할 점은 최소힙과 최대힙 중 한곳에서 팝해준 뒤에 다른 힙에서는 remove 연산을 해줘야한다는 것이다.

또한 최대힙을 구현하기위해서는 데이터를 -를 붙여서 heappush해주고, 빼준뒤에는 다시 -를 붙여줘야 원래 데이터의 값이 나온다. => -를 붙인 데이터를 최소힙에서 찾아서 remove해주면 된다.

 

새로 알게된 heapq의 함수

- heapq.nlargest(n, heap)

heap에서 큰 순서대로 n개의 수를 뽑아준다.

- heapq.nsmallest(n, heap)

heap에서 작은 순서대로 n개의 수를 뽑아준다.

- heapq.heapify(heap)

list를 heap자료로 변환 (선형시간)

import heapq

def solution(operations):
    answer = []
    minh = []
    maxh = []
    for operation in operations:
        com, data = operation.split()
        if com == 'I':
            heapq.heappush(minh, int(data))
            heapq.heappush(maxh, -int(data))
        elif com == 'D':
            if len(minh) == 0:
                continue
            if data[0] == '-':
                minvalue = heapq.heappop(minh)
                maxh.remove(-minvalue)
            else:
                maxvalue = -heapq.heappop(maxh)
                minh.remove(maxvalue)
    if len(minh) == 0:
        return [0, 0]
    answer = [-heapq.heappop(maxh), heapq.heappop(minh)]
    return answer

 

docs.python.org/ko/3/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.9.4 문서

 

programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스