프로그래머스 - 더 맵게(Python)

문제 설명

알고리즘 고민

가장 작은 두 값을 섞어 새로운 스코빌 지수를 가진 음식으로 만드는 것을 반복하는 문제이다. 작은 값 두 개를 찾는 것을 MIN으로 찾기에는 시간이 부족할 듯하여 heap을 사용하여 해결하였다. 18번 케이스에서 막혔는데 만약 처음부터 가장 작은 스코빌 지수의 음식이 K보다 높은 지수라면 굳이 while문을 돌릴 필요 없이 해결할 수 있다. 

코드

 

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