[Python] 프로그래머스 더 맵게

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

프로그래머스

 

풀이

모든 음식의 scoville 값을 K 이상으로 만들고 싶습니다. K보다 작은 경우 (가장 맵지 않은 음식의 스코빌레 + 두번째로 맵지 않은 음식의 스코빌레 * 2)로 새로운 음식을 만듭니다.

 

우선순위 큐(최소힙)를 사용하여 문제를 해결할 수 있습니다.

 

scoville를 최소힙으로 만들면 첫번재, 두번째 원소를 사용해 새로운 음식을 만들면 됩니다.

이 때, 두번째 원소가 scoville에 에 존재하지 않는 경우 해당 음식은 기준을 만족할 수 없으므로 -1을 리턴합니다. 

최소값이 기준값 K 이상이면 while문을 종료하고 정답을 리턴합니다. 

 

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville:
        first = heapq.heappop(scoville)
    
        if first >= K: break
        
        if scoville:
            second = heapq.heappop(scoville)
            heapq.heappush(scoville, first + second * 2)
        else:
            return -1
        
        answer += 1
                
    return answer