문제 링크

풀이

스코빌 지수가 가장 낮은 두 음식을 섞어야하므로, 주어지는 음식들을 오름차순으로 정렬해야한다.
그리고, 두 음식을 섞은 새로운 음식이 생겨도 스코빌 지수 목록은 오름차순으로 정렬이 유지되어야 한다.

하지만 음식을 섞을 때마다 정렬을 하는 방식으로 구현하면, 시간 복잡도가 매우 커진다.
Arrays.sort()를 사용하면 최소 O(N log N), 최대 log(N^2)의 시간 복잡도를 가지게 된다.

따라서 우선순위 큐를 사용한다.
우선순위 큐는 삽입과 삭제(제일 앞에 값 뽑기)시 O(log N)의 시간 복잡도를 가지며, 우선순위가 가장 높은 요소를 먼저 꺼내는 특징이 있다. (기본적으로 가장 작은 값을 먼저 꺼낸다.)

scoville 배열의 요소들을 모두 우선순위 큐에 넣는다. 이때, 최대 값이 10^6이므로 음식을 섞으면 int 범위를 넘어갈 수도 있으니 계산의 편의를 위해 미리 long으로 형변환을 해준다.

PriorityQueue<Long> pq = new PriorityQueue<>();
for(int i : scoville) {
	pq.offer((long) i);
}

우선 순위 큐의 가장 작은 값이 K 이상일 때까지 반복문을 돌며 음식을 섞는다.
이때, 음식이 1개 밖에 안남은 경우 더이상 섞을 수 없으므로 -1을 반환한다.

while(pq.peek() < K){
            if(pq.size() < 2) return - 1;
            Long first = pq.poll();
            Long second = pq.poll();
            pq.offer(first + second * 2);
            answer++;
        }
        

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for(int i : scoville) {
            pq.offer((long) i);
        }
        
        while(pq.peek() < K){
            if(pq.size() < 2) return - 1;
            Long first = pq.poll();
            Long second = pq.poll();
            pq.offer(first + second * 2);
            answer++;
        }
        
        return answer;
    }
}