https://school.programmers.co.kr/learn/courses/30/lessons/42626
힙을 사용하여 가장 작은 두개의 값을 뽑자!!
import heapq
def solution(scoville, k):
heapq.heapify(scoville)
cnt = 0 # 섞은 횟수
while scoville:
s1 = heapq.heappop(scoville)
if s1 < k: # 우선순위큐 안에 가장 작은 숫자 s1이 k미만인경우 --> 섞기
try:
s2 = heapq.heappop(scoville)
except: # scoville에서 뽑은 s1이 k보다 작고 scoville 배열이 비어있어 pop을 못하는 경우 --> 모든 음식의 스코빌 지수를 k이상으로 만들 수 없는 경우이므로 -1 return
return -1
heapq.heappush(scoville, s1 + s2*2) # s1과 s2 섞기.
cnt += 1
else: # 우선순위큐 안에 가장 작은 숫자 s1이 k이상인경우 --> 모든 음식의 스코빌 지수가 k이상이므로 cnt를 return
return cnt
import heapq
def solution(scoville, k):
answer = 0
heapq.heapify(scoville)
while 1:
min1 = heapq.heappop(scoville)
if min1 >= k:
break
elif len(scoville) == 0:
answer = -1
break
min2 = heapq.heappop(scoville)
new_scoville = min1 + 2 * min2
heapq.heappush(scoville, new_scoville)
answer += 1
return answer