[프로그래머스] - 더 맵게 Java

문제설명

• 2개 이상의 스코빌 지수를 입력받는다.
• 스코빌 지수 K를 입력받는다.
• 스코빌 지수를 혼합하여 스코빌 지수가 가장 작은 값이 K와 같거나 커지는 횟수를 구한다.

스코빌 지수 혼합식

가장 작은 스코빌 지수 = (가장 작은 스코빌 지수) + (두번째 작은 스코빌 지수 * 2)

풀이

매 반복 (매 혼합)마다 가장 작은 스코빌 지수와 그 다음 작은 스코빌 지수를 알아야 한다.

매 반복마다 Arrays.sort를 수행하는 것은 매우 비효율적이다.

오름차순으로 데이터를 유지할 수 있는 최소힙을 사용한다.

Java는 우선순위 큐를 이용해서 쉽게 최소힙을 구현할 수 있다.

Code

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소힙
        
        for (int i=0;i<scoville.length;i++) {
            pq.offer(scoville[i]);
        }
        
        while(pq.peek() < K) {
            if (pq.size() <= 2) { // 힙의 크기가 2이하인 경우 반복(혼합) 종료
                break;
            }
            int s1 = pq.poll(); // 스코빌지수 최소값
            int s2 = pq.poll(); // 스코빌지수 두번째 최소값
            int newScoville = s1 + (s2 * 2); // 혼합
            pq.offer(newScoville);
            
            ++answer;
        }
        
        // 두 개가 남을 때까지 혼합했지만 K를 넘지 못했을 때 마지막 두 개 남은 값을 혼합한다 
        if (pq.size() == 2 && pq.peek() < K) { 
            int s1 = pq.poll();
            int s2 = pq.poll();
            if (s1 + (s2*2) >= K) answer++; // 혼합 후 K를 넘었다면 ++
            else return -1; // 혼합한 결과 K를 넘지 못한다면 -1
        }
        
        return answer;
    }
}

보충

최대힙 구성하기

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder)