문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
[ 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) ]
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한사항
-
scoville의 길이는 2 이상 1,000,000 이하입니다.
-
K는 0 이상 1,000,000,000 이하입니다.
-
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
-
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
Solution
처음에는 단순히 리스트를 정렬해가며 풀었는데 정확성은 다 맞았지만 효율성에서 모두 시간초과가 났다.
알고보니 heapq를 이용해 풀어야 하는 문제였다..
#1. 섞은 횟수 저장하는 변수 answer 생성.
scoville 배열을 heapq 모듈의 heapify() 함수를 통해 힙으로 만들어 준다.
#2. 힙 내의 제일 작은 수가 원하는 스코빌 지수 k를 넘을 때까지 반복
#3. 두 개의 음식을 섞는 식을 연산한 후 result 라는 변수에 저장
scoville 힙에 result 넣어줌 (heappush를 해주면 제일 작은 값이 알아서 scoville[0]에 들어간다.)
#4. scoville에 원소가 하나 남아서 더 이상 섞을 수 없는데 그 값이 아직 원하는 스코빌 지수 k 보다 작다면 -1 반환
#5. 성공했으면 섞은 횟수 저장된 answer 변수 반환
Python Code (시간 초과)
Python Code (정답)
