[python] 더 맵게

프로그래머스 python 알고리즘 문제풀이 [ 더 맵게 ] 편.

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

나의 풀이

import heapq
def solution(sco, k):
    heapq.heapify(sco)
    count = 0
    
    while (sco[0]  < k) :
        if len(sco) <= 1 :
            return -1 
        first = heapq.heappop(sco)
        second = heapq.heappop(sco)
        mix_food = first + (second * 2 )
        heapq.heappush(sco, mix_food)
        count += 1 
        
    
    return count

• 우선순위 큐에 자주 사용되는 heap을 사용한 풀이이다.
• heapq 모듈을 import해야 사용할 수 있다.
• 기본적으로 heapify 를 이용하면 하나씩 heappush를 하지 않아도, 리스트를 한번에 힙으로 변환할 수 있다.
• heap[0] - 힙의 0번째 인덱스를 조회하면 가장 작은 값이 조회된다.
• heappop 을 통해 가장 작은 값을 조회 및 팝(꺼내오기) 시킬 수 있다.
• heappush를 통해 힙에 원소를 하나씩 넣을 수 있다.
• 힙의 젤 작은 값이 K보다 작다면 계속 while 문이 돌아가고 count는 1씩 더해지는 구조이다.
• 하지만 만약 while문의 조건문을 통과했고 sco (힙) 의 길이가 1보다 같거나 작다면, 원소가 하나밖에 없으므로 더 이상 섞기를 진행하지 못하는 상태를 뜻하므로 -1을 반환시킨다.
• while문을 정상적으로 통과한다면 sco[0] >= k가 성립한 것이므로 count 를 반환한다.