# scoville = [1, 2, 3, 9, 10, 12], K = 7 -> 2
# 스코빌 지수가 1인 음식과 2인 음식을 섞었을 때 되는 음식의 스코빌 지수
# -> 새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
# -> 가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
# 스코빌 지수가 3인 음식과 5인 음식을 섞었을 때 되는 음식의 스코빌 지수
# -> 새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
# -> 가진 음식의 스코빌 지수 = [13, 9, 10, 12]
# -> 모든 음식의 스코빌 지수가 7 이상으로 됨
# => 섞은 횟수: 2회
## 의사코드 ##
# import heapq
# -> 주어진 scoville을 최소 힙 형태로 정렬한 다음 사용
# 가장 맵지 않은 음식의 스코빌 지수 = heapq.heappop(scoville)
# -> scoville의 최솟값인 scoville[0]을 반환해서 first에 저장하고, scoville에서 삭제 후 다시 scoville[0]에 scoville의 최솟값을 정렬
# 두 번째로 맵지 않은 음식의 스코빌 지수 = heapq.heappop(scoville)
# -> scoville의 최솟값인 scoville[0]을 반환해서 second에 저장하고, scoville에서 삭제 후 다시 scoville[0]에 scoville의 최솟값을 정렬
# 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
# heapq.heappush(scoville, new)
# -> scoville에 섞은 음식의 스코빌 지수를 추가하고, 다시 scoville[0]에 scoville의 최솟값을 정렬
# 섞은 횟수 -> 반복문 돌리면서 cnt += 1
# 모든 음식의 스코빌 지수가 K 이상이면 break -> 스코빌 지수가 K보다 작은 경우 반복문 실행
# +
# 새로운 스코빌 지수가 추가된 후의 가진 음식의 스코빌 지수 배열이 입출력 예시 설명에 나온 순서 그대로 진행되어야 될 필요 없음
# -> heapq는 최소 힙 형태로 정렬하는 거라서 index:0인 값에 최솟값을 정렬해 주고 그 뒤에 나오는 값들은 정렬 x
# (최소 힙은 최솟값을 빠르게 찾기 위한 알고리즘이지, 작은 순서대로 정렬하는 알고리즘 X!)
# 어차피 우리는 스코빌 지수 배열에서 최솟값만 계속 꺼내면 됨
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville) # scoville을 최소 힙 형태로 정렬
for s in scoville:
# 스코빌 지수가 K보다 작은 경우
if s < K:
first = heapq.heappop(scoville) # 가장 맵지 않은 음식의 스코빌 지수
second = heapq.heappop(scoville) # 두 번째로 맵지 않은 음식의 스코빌 지수
new = first + (second * 2) # 섞어 만든 새로운 음식의 스코빌 지수
heapq.heappush(scoville, new) # 새로운 스코빌 지수를 scoville에 삽입
answer += 1 # 섞은 횟수 + 1
return answer
-> 추가 테스트 케이스 & 효율성 테스트 실패
'모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return' 부분을 까먹음...
통과한 코드
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville) # scoville을 최소 힙 형태로 정렬
# 스코빌 지수가 K보다 작은 경우
while scoville[0] < K:
first = heapq.heappop(scoville) # 가장 맵지 않은 음식의 스코빌 지수
second = heapq.heappop(scoville) # 두 번째로 맵지 않은 음식의 스코빌 지수
new = first + (second * 2) # 섞어 만든 새로운 음식의 스코빌 지수
heapq.heappush(scoville, new) # 새로운 스코빌 지수를 scoville에 삽입
answer += 1 # 섞은 횟수 + 1
# 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
if len(scoville) == 1 and scoville[0] < K:
return -1 # -1을 return
return answer
-> '모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return' 추가
'모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우' => scoville에 하나의 원소만 있고, scoville[0]이 K보다 작은 경우
과정 확인
# scoville = [1, 2, 3, 9, 10, 12, K = 7
"""
정렬된 scoville: [1, 2, 3, 9, 10, 12]
__________________________________________________
first: 1
second: 2
남은 scoville: [3, 9, 10, 12]
새로운 스코빌: 5
추가된 scoville: [3, 5, 10, 12, 9]
__________________________________________________
first: 3
second: 5
남은 scoville: [9, 12, 10]
새로운 스코빌: 13
추가된 scoville: [9, 12, 10, 13]
__________________________________________________
"""
