[프로그래머스] 더 맵게 - 파이썬/python

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같은 방법으로 섞어 새로운 음식을 만든다. 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶을 때, 섞어야 하는 최소 횟수를 구하는 문제다.

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

 

제한사항

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

 

예시

scoville: [1, 2, 3, 9, 10, 12]
K: 7
return: 2

 

풀이

힙 자료구조를 활용하여 풀어보았다.

👉 최소 힙에서는 항상 가장 작은 값이 루트(scoville[0])에 위치한다.

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        n1 = heapq.heappop(scoville)
        n2 = heapq.heappop(scoville)
        n = n1 + n2 * 2

        heapq.heappush(scoville, n)
        answer += 1   
        
        # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1
        if scoville[0] < K and len(scoville) == 1: 
            return -1        
    
    return answer

• 주어진 리스트를 힙 구조로 변환한다.
• 힙의 최상단에 위치한 스코빌 지수가 K보다 클 때까지 반복문을 실행한다.
  • 힙에서 가장 작은 두 개의 음식을 꺼내 주어진 방법으로 섞어 새로운 스코빌 지수를 계산한다.
  • 새로 만들어진 음식의 스코빌 지수를 힙에 다시 넣어주고 섞은 횟수를 증가시킨다.
• 만약 더 이상 섞을 음식이 없는데 가장 작은 스코빌 지수가 K보다 작다면 -1을 반환한다.
• 모든 음식의 스코빌 지수가 K보다 크다면 섞은 횟수를 반환한다.