[Level 2] [Java] 더 맵게

문제

매운 것을 좋아하는 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. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

문제 풀이

힙을 이용한 문제입니다. 최소 힙에 대한 이해가 있으시면 문제를 푸는데 어려움은 없으셨을 겁니다.

기본적으로 힙을 이용한 문제가 나오면 PriorityQueue를 이용해 문제를 해결합니다.

최소 힙 자체가 정렬된 구조가 아니기 때문에 단순히 sort()를 하는 것보다 시간은 빠르게 나올 것입니다.

 

문제에서 섞은 음식의 스코빌 지수를 위해선 우선순위 큐에는 최소 2개의 값이 있어야 합니다.

그래야 가장 최솟값을 갖는것들을 우선순위 큐에서 빼내올수 있기 때문입니다.

그러면 가장 최소값을 가진 2개의 값을 빼낸 후 섞은 음식의 스코빌 지수를 만들어 다시 PriorityQueue에 저장시킵니다. 

이 과정을 계속 반복해서 스코빌 지수를 K이상 만들 수 있는지 없는지 확인하면 문제는 해결됩니다.

 

Java Code

package com.programmers.java;

import java.util.PriorityQueue;

public class Solution {
    
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] scoville = {1, 2, 3, 9, 10, 12};
        int K = 7;
        
        s.solution(scoville, K);
    
    }
    
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for (int num : scoville) pq.add(num);
        
        boolean flag = false;
        // 맨앞의 음식의 스코빌 지수가 K이상이 될때까지 반복
        while (pq.size() >= 2) {
            int food1 = pq.poll();
            int food2 = pq.poll();
            int newFood = food1 + (food2 * 2);
            pq.add(newFood);
            answer++;
            
            if (pq.peek() >= K) {
                flag = true;
                break;
            }
            
        }
        // 스코빌 지수가 K이상 안되는 경우
        if (!flag)
            answer = -1;
        
        return answer;
    }

}