[Algorithm🧬] 더 맵게

문제 / 풀이.py

import heapq

def solution(scoville, K):
    count = 0
    scoHeap = []
    
    for sco in scoville:
        heapq.heappush(scoHeap, sco)

#   하나 꺼냈을 때,
    first = heapq.heappop(scoHeap)
#   제일 작은게 K보다 작으면서, heap이 비어있지 않으면 들어간다.
    while first < K and len(scoHeap) > 0:
        second = heapq.heappop(scoHeap)
        heapq.heappush(scoHeap, first + second * 2)
        count += 1
        first = heapq.heappop(scoHeap)
    
#.  다 돌고 나왔는데 K보다 작은게 있으면 -1 return
#   여기를 scoHeap의 원소가 K보다 작으면으로 하면 안먹혔던 이유는
#   scoHeap이 이 시점에 비어있을 수 있기 때문.
    if first < K:
        return -1
    
    return count

heap 사용하는 방법이 기억 안나서 찾아봤다. heapq는 기본적으로 minheap 이라고 한다.

heap을 사용하는 것 보다.. 중간 로직이 더 어려웠다.

섞어서 K를 넘을 수 없는거 고려 안했다가 1 3 8 14 오류나고..

len(scoHeap) > 0 안했다가 한번 런타임 에러 나고 (원소 0개 남았는데 pop해서)

조금 잘못 생각해서 len(scoHeap) > 1로 넣었더니 1개 남을 때까지 하는 16번이 통과가 안되고..

그래도 heap을 언제 사용할 지는 확실히 알았다. 반복문과 sort를 사용해서 해결하고 싶은데 효율성 검사가 있는 경우에 사용하면 되겠다.