프로그래머 – 마라탕

매운 음식을 좋아하는 레오는 모든 음식에 대해 Scoville 점수가 K 이상인 것을 원합니다. 모든 음식이 스코빌 점수가 K 이상이 되도록 레오는 아래 그림과 같이 가장 낮은 스코빌 점수를 가진 두 가지 음식을 특별한 방법으로 결합하여 새로운 음식을 만들었습니다.

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

Leo는 모든 음식의 Scoville 점수가 K 이상이 될 때까지 반복해서 섞습니다.
레오의 음식에 대한 Scoville 점수 배열과 원하는 Scoville 지수 K가 주어지면 모든 음식이 K보다 큰 Scoville 지수를 갖기 위해 모든 음식을 혼합해야 하는 최소 횟수를 반환하는 솔루션 함수를 작성합니다.

한계

• 스코빌의 길이는 2보다 크고 1,000,000보다 작습니다.
• K는 0보다 크고 1,000,000,000보다 작거나 같습니다.
• 스코빌의 요소는 모두 0보다 크고 1,000,000보다 작습니다.
• Scoville 점수가 K 이상인 음식이 없으면 -1을 반환합니다.

입력 및 출력 예

스코빌 /K/리턴

I/O 예시 설명

1. Scoville 등급이 1인 식품과 Scoville 등급이 2인 식품을 혼합하면 해당 식품의 Scoville 등급은 다음과 같습니다.
   새로운 음식에 대한 스코빌 지수 = 1 + (2 * 2) = 5
   음식에 대한 Scoville 점수 = (5, 3, 9, 10, 12)
2. Scoville 등급이 3인 식품과 Scoville 등급이 5인 식품을 섞으면 해당 식품의 Scoville 등급은 다음과 같습니다.
   새로운 음식에 대한 스코빌 지수 = 3 + (5 * 2) = 13
   음식에 대한 Scoville 점수 = (13, 9, 10, 12)

모든 식품은 Scoville 점수가 7 이상이며 이중 혼합됩니다.

소스 코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) # min heap
    while True: # 무한 루프
        min1 = heapq.heappop(scoville)
        if min1 >= K: # 최소값이 K 보다 크면 break
            break
        
        elif len(scoville) == 0: # 리스트 길이가 0이면 -1 리턴
            answer = -1
            break
    
        min2 = heapq.heappop(scoville) # 두번째로 안매운 지수
        new_scoville = min1 + 2*min2 # 새 스코빌 지수
        heapq.heappush(scoville, new_scoville) # 삽입
        answer +=1 # 회수 + 1
    
    return answer

설명하다

• 최소 힙 사용
• 무한 루프에서 스코빌 값(min1) 추출 -> 최소 힙에서 추출한 최소값
  • min2는 두 번째로 덜 매운 지수입니다.
  • 레시피에 따라 두 가지를 섞고 heappush에 붓습니다.
  • 무한 루프이기 때문에 중단점에 도달할 때까지 계속 반복됩니다.
  • 매번 대답 + 1