우선순위 큐를 이용해서 푸는 문제였다.
가장 스코빌 지수가 낮은 음식부터 차례로 섞어서 모든 음식을 스코빌 지수 이상으로 만들면 된다.
우선순위 큐에서 뽑으면 그 음식이 스코빌 지수가 가장 낮은 음식이고, 그 음식이 스코빌 지수 K 미만일 시 그 다음으로 스코빌 지수가 낮은 음식과 섞으면 된다.
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> heap = new PriorityQueue<>();
for(int scov : scoville){
heap.add(scov);
}
// 큐가 빌 때까지 실행
while(!heap.isEmpty()){
int a = heap.peek();
// 뽑힌 음식의 스코빌 지수가 K 미만이면
if(a<K){
a = heap.poll();
if(heap.isEmpty()){ // 이건 들어가지 않으면 런타임 에러가 나는데, 아마 큐가 비어있을 때 인 것 같다.
return -1;
}
int b = heap.poll();
int c = calcScoville(a,b);
heap.add(c);
answer++;
}
// 뽑힌 음식의 스코빌 지수가 K 이상이면 모든 음식의 스코빌 지수가 K 이상이다.
else{
return answer;
}
}
return -1;
}
// A와 B 음식을 섞었을 때의 스코빌 지수를 리턴하는 메소드
static int calcScoville(int a, int b){
return a+(b*2);
}
}