매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
입출력 예제
scoville | K | return |
[1,2,3,9,10,12] | 7 | 2 |
입출력 예 설명
우선순위 큐에 음식의 스코빌 지수를 추가한다.
가장 낮은 스코빌 지수가 K 이상이 되기 전까지 두 음식의 스코빌 지수를 섞는다.
힙(heap): 최솟값 또는 최댓값을 빠르게 찾기 위해 완전이진트리 형태로 만들어진 자료구조
Priority Queue(우선순위 큐): 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 것
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(data); queue에 데이터 추가
queue.poll(); //queue에 가장 작은 데이터를 꺼내기
queue.peek(); //queue의 가장 작은 데이터를 확인
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> heap = new PriorityQueue<>();
for(int i:scoville){
heap.add(i);
}
while(heap.peek()<K){
if(heap.size()==1) //값이 2개 이상 있어야 비교 가능
return -1;
int first=heap.poll();
int second=heap.poll();
heap.add(first+(second*2));
answer++;
}
if(heap.peek()<K)
answer=-1;
return answer;
}
}
실행 결과