문제 설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo
는 모든 음식의 스코빌 지수가 K 이상이 될 때까지
반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville
과 원하는 스코빌 지수 K
가 주어질 때, 모든 음식의 스코빌 지수를 K 이상
으로 만들기 위해 섞어야 하는 최소 횟수를 return
하도록 solution 함수를 작성해주세요.
제한 사항
입출력 예
로직(우선순위 큐
로 구현했음)은 간단하지만, 예외 케이스를 해결하지 못해 런타임 에러가 났었다.
예외 케이스
모든 음식을 다 섞어서 마지막에 하나의 음식만 남았는데, 그 음식의 스코빌 지수가 K를 넘지 않을 때이다.
아래의 코드를 보고 이해하길 바란다.
import java.util.*;
class Solution {
PriorityQueue <Integer> q = new PriorityQueue<>();
int [] temp = new int[2];
int cnt = 0;
int mix_num=0;
int first=0;
int sec=0;
public int solution(int[] scoville, int K) {
int answer = 0;
//우선순위 큐에 넣는 과정.
for(int i=0;i<scoville.length;i++){
q.add(scoville[i]);
}
//처음 음식의 스코빌지수가 K이상이면 섞을 필요가 없으므로 0을 리턴
if(q.peek()>=K){
return 0;
}
//그렇지 않다면 음식 두개를 골라 섞어서 다시 큐에 집어넣는다.
while(q.peek()<K){
if(cnt==0){
first = q.remove();
cnt++;
}
if(cnt==1){
sec = q.remove();
cnt++;
}
if(cnt==2){
int mix = first + sec*2;
q.add(mix);
cnt=0;
mix_num++;
}
//예외케이스 처리 부분.
if(q.size()==1 && q.peek()<K){
return -1;
}
}
return mix_num;
}
}