[프로그래머스_Level2] 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

[문제]

매운 것을 좋아하는 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 합니다.

 

[코드]

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer=0; // 섞은 횟수
        PriorityQueue<Integer> pq=new PriorityQueue<>(); // 값 삽입 시 정렬
        
        for(int i:scoville)
            pq.add(i);
        
        while(!pq.isEmpty()) {
            // 가장 작은 값의 스코빌 지수가 k 이상인지 확인
            if(pq.peek()>=K)
                return answer;
            
            // 가장 작은 값의 스코빌 지수가 k 미만이면서 더 이상 음식을 섞을 수 없는 경우
            if(pq.size()==1)
                return -1;
            
            // 음식 섞기
            answer++;
            int a=pq.poll();
            int b=pq.poll();
            
            pq.add(a+(b*2));
        }
        return answer;
    }
}

 

[고찰]

 이번 문제는 우선순위 큐를 사용하는 문제였다. 내림차순으로 정렬된 값들에서 두 개를 꺼내 섞은 후 다시 큐에 삽입하는 과정을 반복하면 되는데 이때 가장 작은 값을 갖는 스코빌 지수가 K 이상인 경우 반복문에서 빠져나온다.

 주의해야 할 점은 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 출력해야 하므로 가장 작은 스코빌 지수가 K 미만이면서 우선순위에 남아있는 음식이 1개라면 -1을 return 해야 한다. 해당 부분을 넣어주지 않으면 런타임 오류가 난다.