문제
주어지는 모든 음식의 스코빌 지수를 K이상으로 만들기 위해
스코빌 지수가 가장 낮은 음식 두 개를 섞어서 새로운 음식을 만든다.
모든 음식의 스코빌 지수가 K 이상이 되도록 만들자.
\(스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)\)
음식들의 스코빌 지수를 담은 배열 : scoville
원하는 스코빌 지수 : K
scoville의 길이는 1이상 1,000,000 이하
K는 0이상 1,000,000,000 이하
scoville의 원소는 각각 0이상 1,000,000 이하
모든 음식의 스코빌 지수를 K이상으로 만들수 없는 경우 -1
입출력 예시
| scoville | K | return |
|---|---|---|
| [1, 2, 3, 9, 10, 12] | 7 | 2 |
접근
힙을 이용하면 간단하게 구현할 수 있다.
가장 작은 음식 두개를 힙에서 꺼내고, 스코빌 지수 연산을 한 후 다시 힙에 넣는다.
이 과정을 힙에서 꺼낸 값이 K보다 커질 때 까지 반복하면 된다.
힙이 빌 때까지 반복하게 된다면 조건을 만족할 수 없으므로, -1을 리턴한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while True:
minItem = heapq.heappop(scoville)
if minItem >= K:
break
if len(scoville) < 1:
answer = -1
break
newItem = heapq.heappop(scoville) * 2 + minItem
heapq.heappush(scoville, newItem)
answer += 1
return answer