[프로그래머스 42626 파이썬] 더 맵게 (level 2, 힙)

알고리즘 유형 : 힙
풀이 참고 없이 스스로 풀었나요? : O

https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3

소스 코드(파이썬)

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

풀이 요약

1. 최소 힙을 사용한 풀이이다.

   scoville을 최소 힙으로 만들고, 힙에 요소가 2개 이상 들어있고, 최솟값이 K보다 아직 작은 동안 계속 반복하여 음식 섞기를 수행한다.

2. 매 단계에서, 힙에서 두 개를 뽑는다. 이 두 개로 음식 섞기를 수행한 후 힙에 추가하고 answer에 횟수를 1 추가해준다.

3. 반복문이 종료되는 시점은 두 가지이다.

   1) 힙에 요소가 1개 이하가 된 경우

   이 경우, 더 이상 음식을 섞지 못한다. 남은 하나의 음식을 이제 K와 비교만 해주면 된다. 만약 K보다 작으면 실패한 경우이므로 -1을 리턴한다.

   2) 최솟값이 K 이상이 된 경우

   이 경우, 더 이상 음식을 섞지 않아도 된다. 음식 중 가장 작은 스코빌이 K 이상이 되었으므로 이는 곧 모든 음식의 스코빌이 K 이상이 되었단 의미이기 때문이다. 이 때는 answer를 그대로 리턴하게 된다.

배운 점, 어려웠던 점

• 최소 힙으로 쉽게 풀 수 있는 문제였다.