프로그래머스 - 더 맵게

1. 문제

문제 링크

2. 풀이

2-1. 조건

1. 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우에는 -1을 return

2-2. 풀이

가장 쉽게 떠오를 수 있는 방법은
모든 음식들의 스코빌 지수가 K가 넘을 때까지
음식들을 스코빌 지수를 기준으로 정렬한 다음에
스코빌 지수가 낮은 두 개의 음식을 문제의 요구대로 섞어주는 방법일 겁니다.

하지만 이 방법으로는 매번 정렬에 필요한 시간 복잡도는 NlogN이고
음식을 섞어야하는 횟수도 최악의 경우에는 n이 되므로
총 시간 복잡도는 N^2logN이 되어버립니다.

이 때 사용할 수 있는 자료구조가 우선순위큐 입니다.
우선순위큐는 힙 자료구조로 구현되어있는 자료구조입니다.
우선순위큐는 데이터에서 최솟값이나 최댓값을 찾는데 logN의 시간밖에 들지 않기 때문에
총 시간 복잡도는 NlogN이 됩니다.

그러면 우리는 이 우선순위큐를 활용해서 계획을 세워보겠습니다.

1. 모든 음식들을 우선순위큐에 넣습니다.
2. 우선 순위큐에서 peek 메소드를 통해 제일 낮은 스코빌 지수가 K보다 크거나 같다면 모든 음식의 스코빌 지수가 K보다 크다는 뜻이므로 루프를 탈출합니다.
3. 만약 음식이 하나만 남았고 하나 남은 음식의 스코빌 마저 K보다 작다면 -1을 리턴합니다.
4. 3, 4에도 해당하지 않는다면 스코빌 지수가 차례로 제일 낮은 두 개의 음식을 섞어줍니다.

3. 전체 코드

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int solution(int[] scoville, int K) {
        Queue<Integer> pq = new PriorityQueue<>();
        int ans = 0;
        
        // 1. 모든 음식들을 우선순위큐에 넣습니다.
        for (int i = 0; i < scoville.length; i++) {
            pq.add(scoville[i]);
        }
        
        while (true) {
                // 2. 우선 순위큐에서 peek 메소드를 통해 제일 낮은 스코빌 지수가 K보다 크거나 같다면
                // 모든 음식의 스코빌 지수가 K보다 크다는 뜻이므로 루프를 탈출합니다.
        	if (pq.peek() >= K) break;
            
                // 3. 만약 음식이 하나만 남았고 하나 남은 음식의 스코빌 마저 K보다 작다면 -1을 리턴합니다.
        	if (pq.size() == 1 && pq.peek() < K) {
        		ans = -1;
        		break;
        	}
            
                // 4. 3, 4에도 해당하지 않는다면 스코빌 지수가 차례로 제일 낮은 두 개의 음식을 섞어줍니다.
        	pq.add(pq.poll() + pq.poll()*2);
        	ans++;
        }
        
        return ans;
    }
}