[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

 

 

풀이

import java.util.*;


class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();

        // scoville 배열을 minQueue에 넣어주기
        for (int i = 0; i < scoville.length; i++) {
            minQueue.offer(scoville[i]);
        }

        // 제일 안매운 + 두번째로 안매운 스코빌
        int one = 0; // 제일 안매운
        int two = 0; // 두번째로 안매운

        int a = 0; // one + two * 2 의 값을 넣어줄 변수

        // i < 1000000 -> 배열 길이가 1000000로 주어짐.
        for (int i = 0; i < 1000000; i++) {

            // 처음부터 모든 배열이 K 보다 클 경우 바로 break
            if (minQueue.peek() >= K){
                break;
            }

            // size가 1이 라는건 모두 섞어도 K를 넘지 못했다는 의미기 때문에 -1을 넣고, break
            if (minQueue.size() == 1){
                answer = -1;
                break;
            }

            // one, two에 넣고 삭제
            one = minQueue.poll();
            two = minQueue.poll();

            a = one + (two * 2);

            // k 보다 작으면 반복. 섞은 값 a를 다시 넣어준다.
            if (a < K){
                answer++;
                minQueue.offer(a);
            }

            // a가 k보다 크거나 같을 경우
            else if (a >= K) {
                // 맨 마지막 one, two를 반환&제거 하면 minQueue.size == 0 이됨.
                if ( minQueue.size()==0){
                    answer++;
                    break;
                } 
                // 남아있는 배열 중 제일 작은 수를 반환했을 때 k보다 크거나 같으면 더이상 섞을 필요가 없기 때문에 break.
                else if (minQueue.peek() >= K) {
                    answer++;
                    break;
                } 
                // 남아있는 배열 중 제일 작은 수를 반환했을 때 k보다 작으면 그 수를 다시 섞어야 하기때문에 배열에 a 넣은 후 반복.
                else if (minQueue.peek() < K) {
                    answer++;
                minQueue.offer(a);
                }
            }

        }


        return answer;
    }
}

 

 

반례

scoville	K	return
[1,1,1,10]	9	3
[10,10,10,10]	1	0