[프로그래머스][힙(Heap)] 더 맵게

내가 푼 풀이

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while len(scoville) > 1 and (scoville[0] < K):
        min_first = heapq.heappop(scoville)
        min_second = heapq.heappop(scoville)
        heapq.heappush(scoville, min_first + min_second*2)
        answer += 1
    if scoville[0] < K:
        answer = -1
    return answer

이 문제는 제일 스코빌지수가 제일 작은 값의 정보를 값이 추가될 때마다 갱신해야하므로, 우선순위 큐를 이용하여 푸는 것이 바람직하다. 파이썬에서는 우선순위 큐를 사용하기 위해서는 Heapq를 이용하는 방법과 PriorityQueue를 이용하는 방법이 있다.

Heapq vs PriorityQueue

두 방법의 가장 큰 차이점은 PriorityQueue는 thread-safe하지만 Heapq는 그렇지 않다는 것이다. PriorityQueue는 heapq를 사용하는 동시에 Queue 클래스의 Locking을 이용해 thread-safe하게 만든다. 따라서 multiple thread의 상황에서는 PrioirityQueue를 이용하는 것이 적절하다. Heapq는 thread-safe를 보장하지 않지만, 실행속도가 좀 더 빠르다.
위의 문제 풀이와 같은 상황에서는 multiple thread 상황이 아니며 실행속도가 중요하므로 heapq 방법을 사용했다.

출처) What's the difference between heapq and PriorityQueue in python?
https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-python

Heapq

모듈 임포트

import heapq

를 이용하여 간편하게 모듈을 임포트 할 수 있다.

push, pop 방법

import heapq
heap = []
heapq.heappush(heap, 1)
heapq.heappop(heap)

heapq.heappush(리스트, 넣을 원소)
heapq.heappop(리스트)
를 통해 원소를 넣고, 뺄 수 있다.

pop하지 않고 최소값을 확인하는 방법

heap[0]

0번째 인덱스의 원소는 최소값을 항상 가지지만, 1번째, 2번째 인덱스의 원소가 그 다음 최소값이라는 것은 보장되지 않는다는 것에 주의하자.

기존 리스트를 힙으로 바꾸는 방법

heapq.heapify(리스트)

를 이용하면 기존 선언해두었던 리스트도 우선순위 큐처럼 사용할 수 있다.
위의 문제에서는 scoville 리스트를 heapify를 통해 우선순위 큐처럼 사용하였다.

내림차순으로 Heap 정렬하기

heapq에서는 넣은 값을 기준으로 항상 오름차순 정렬하기 때문에, 원소에 (우선순위, 값)인 튜플을 넣음으로써 내림차순으로 정렬할 수 있다.

heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

이렇게 음수값을 취한 튜플을 원소로 넣어주면, 절대값이 큰 값부터 내림차순 정렬이 된다. 정렬한 값은

heapq.heappop(heap)[1]

으로 튜플의 1번째 요소를 가져옴으로써 얻을 수 있다.