문제 설명
매운 것을 좋아하는 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 합니다.
입출력 예
| scoville | K | return |
|---|---|---|
| [1, 2, 3, 9, 10, 12] | 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 def solution(scoville, K): answer = 0 heapq.heapify(scoville) while 1: if len(scoville) == 1 and scoville[0] < K: return -1 if scoville[0] >= K: return answer smallest = heapq.heappop(scoville) second = heapq.heappop(scoville) new = smallest + 2*second heapq.heappush(scoville, new) answer += 1
문제에 주어진 과정을 그대로 따라간 풀이이다.
우선 scoville을 heapify한다.
heapify는 리스트(꼭 리스트여야 한다)를 heap 자료구조에 맞게 재배열한다.
쉽게 말해서 힙구조에서의 정렬이다.
while문의 첫 번째 if는 scoville이 길이가 1이고 요솟값이 K보다 작은지 묻고있다.
만약 그렇다면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이기 때문에 -1을 리턴한다.
섞은 음식의 스코빌 지수는 가장 맵지 않은 음식과 두 번째로 안 매운 음식의 스코빌 지수의 합이므로 스코빌 지수가 갑자기 감소할 일은 없다.
두번째 if문은 scoville의 첫 번째 요솟값이 K 이상인지를 묻는다.
heap 구조에서는 첫 번째 인자가 최솟값이므로 이 값이 K 이상이면 모든 음식의 스코빌 지수가 K 이상이다.
이 때는 answer을 반환한다.
answer는 0으로 초기화했는데 섞을 때마다 1을 더해줄 것이다.
그 아래서는 섞는 과정을 보여준다.
smallest에 scoville에서 heappop한 값을 대입하고 그 다음에 second에 scoville에서 다시 heappop한 값을 대입한다.
각각에는 현재 scoville의 최솟값, 두 번째로 작은 값이 대입된다.
이 둘을 문제 조건에 맞게 더해준 뒤 new에 대입한다.
그리고 이 값을 heap 자료구조에 맞게 scoville에 넣어주기 위해 heappush를 이용한다.
한 번 섞었기 때문에 answer에 1을 더해준다.
효율성 테스트: ~1880.40ms / 51.8M
