매운 음식을 좋아하는 레오는 모든 음식에 대해 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/리턴
| (1, 2, 3, 9, 10, 12) | 7 | 2 |
I/O 예시 설명
- Scoville 등급이 1인 식품과 Scoville 등급이 2인 식품을 혼합하면 해당 식품의 Scoville 등급은 다음과 같습니다.
새로운 음식에 대한 스코빌 지수 = 1 + (2 * 2) = 5
음식에 대한 Scoville 점수 = (5, 3, 9, 10, 12) - 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