프로그래머스: 더 맵게

문제

코딩테스트 연습 - 더 맵게

 

문제 풀이

 모든 음식의 스코빌 지수를 K 이상으로 만들 고자 하는데 최소 몇 번 음식을 섞어야 하는지 반환하는 문제이다. 이 문제를 풀기 위해서는 `heapq`를 사용하면 쉽게 해결할 수 있다. `heapq`는 루트 노드가 가장 작은 값을 가지게 되기 때문이다. 따라서 `heapq`를 이용해 가장 작은 값 2개를 가져온 후 문제의 조건에 맞게 음식을 섞은 후 다시 `heapq`에 삽입한다. 이 과정에서 `heapq`는 heap의 성질을 따르기에 맵기의 크기에 따라 자동으로 적절한 위치에 삽입된다.

 

 더 이상 섞을 수 없거나, 루트 노드가 K보다 작을 때 까지 반복하면 문제에서 찾고자 하는 답을 찾을 수 있다.

 

 

코드

import heapq


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

    return answer if scoville[0] > K else -1