프로그래머스|더 맵게

문제설명

음식들의 매운 정도인 스코빌과 기준치인 K를 입력받고 모든 음식들의 스코빌이 K이상이 되도록 음식들을 조합하고 그렇게 만드는 데 필요한 조합의 횟수를 출력하는 문제입니다. (음식들을 조합하는 방법은 가장 스코빌이 낮은 음식과 그 다음으로 낮은 음식을 조합하면 (가장 낮은 스코빌+두 번째로 낮은 스코빌*2)의 음식이 생기는 방식입니다.)

​

작동 순서

1. 입력받은 스코빌을 힙으로 변환합니다.

2. 가장 낮은 스코빌이 K보다 낮은 동안 반복문을 실행합니다.

3. 가장 스코빌이 낮은 음식을 min1으로 지정합니다.

4. 그 다음 스코빌이 낮은 음식을 min2로 지정합니다.

5. 새로 조합하여 나온 음식을 scoville 힙에 추가하고 횟수에 1을 더합니다.

6. 가장 낮은 스코빌이 K보다 높아지면 반복문을 종료하고 조합 횟수를 반환합니다.

7. 이런 식으로반복하다가 음식이 하나 밖에 남지 않았는데 그 음식의 스코빌이 K보다 작은 경우 -1을 반환합니다.

​

​

소스코드

import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        min1 = heapq.heappop(scoville)
        min2 = heapq.heappop(scoville)
        new = min1 + min2 * 2
        heapq.heappush(scoville, new)
        answer += 1
        if len(scoville) == 1 and scoville[0] < K:
            answer = -1
            break
    return answer


food = list(map(int, input().split()))
k = int(input())
print(solution(food, k))