[프로그래머스] 더 맵게 - Heap (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 합니다.

입출력 예

[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회입니다.

 

---

1) 처음 풀었던 방법:

ArrayList 사용해서 무려 매번 Sort 하는 방법을 사용.

정확도는 100% 였으나, 효율성에서 0점을 기록했다.

PriorityQueue를 써보라는 힌트를 얻고 다시 도전.

+ Sort 를 하지 않는 방법도 써봤는데 실패했다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {        
        int answer = 0;
        
        ArrayList<Integer> scovilleArr = new ArrayList<>();
        for(int food : scoville)
            scovilleArr.add(food);
        Collections.sort(scovilleArr);
        
        int minScoFood =0, nextMinScoFood =1;
        while(true){
            //sort 후 최소값이 K 이상인지 확인
            Collections.sort(scovilleArr);
            if(scovilleArr.get(minScoFood)>=K)
                break;
            else if (scovilleArr.size()==1)
                return -1;
            
            // iteration 추가
            answer++;

            //새로운 스코빌 값 생성
            int newScoville = scovilleArr.get(minScoFood) + (scovilleArr.get(nextMinScoFood)*2);
            scovilleArr.add(newScoville);
            
            //기존의 두 음식 삭제. 
            //2번째로 맵지 않은 음식 먼저 삭제:가장 안매운 음식 삭제할 경우 배열의 순서가 바뀌게 됨.
            scovilleArr.remove(nextMinScoFood); 
            scovilleArr.remove(minScoFood); 
        }
        return answer;
    }
}

2) 그 다음 방법:

PriorityQueue를 결국 사용!

간단히 해결했다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {        
        int answer = 0;
        
        PriorityQueue<Integer> scovilleQ = new PriorityQueue<>();
        for(int food : scoville)
            scovilleQ.add(food);
        
        while(true){
            //sort 후 최소값이 K 이상인지 확인
            if(scovilleQ.peek()>=K)
                break;
            else if (scovilleQ.size()==1)
                return -1;
            
            // iteration 추가
            answer++;

            //새로운 스코빌 값 생성, 기존의 두 음식 삭제.
            int newScoville = scovilleQ.peek();
            scovilleQ.poll();
            newScoville += (scovilleQ.peek()*2);
            scovilleQ.poll();
            scovilleQ.offer(newScoville);
        }
        return answer;
    }
}