[프로그래머스 고득점 Kit/Java] 더 맵게

 

배열의 모든 값이 K(스코빌 지수) 이상이 될 때까지

가장 낮은 두 개의 음식을 특별한 방법으로 섞는다.

가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 한다.

 

원래는 ArrayList를 만들어 스코빌 지수를 넣고

매번 정렬을 하려고 했다.

그러나 시간 + 정확도 테스트에서 모두 점수를 제대로 받지 못했다.

 

그러던 중 우선순위 큐를 사용해야 함을 알게 됐다.

우선순위 큐는 일반적인 큐와 달리, 들어가는 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가므로

따로 정렬을 해줄 필요가 없어 기존 방식에 비해 훨씬 효율적이다.

 

// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>();
 
// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

 

이걸 이용해서 해결한 방식은 다음과 같다.

PriorityQueue 사용

import java.util.*;
import java.io.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int scov : scoville) {
            pq.offer(scov);
        }
        
        while (true) {
            int first = pq.poll();
            if (first >= K) return cnt;
            if (pq.size() < 1) return -1;
            int second = pq.poll();
            pq.offer(first + (second * 2));
            cnt++;
        }
    }
}

 

여기서 또 하나 주의할 점이 있었는데,

문제에서 "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return" 하라고 했다.

 

따라서 첫 번째 숫자(가장 낮은 스코빌 지수)가 K 이하인데,

pq의 size가 1보다 작다면 (모든 수를 다 poll했는데도 K 이상이 없었다면) -1을 return 해준다.