프로그래머스 - 더 맵게(Heap) / Level 2 / Java

문제 📋

프로그래머스 - 더 맵게

풀이 📝

import java.util.*;

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

1. 문제 정의
   스코빌 지수가 정렬된 채로 주어졌을 때
   가장 낮은 것과 두 번째로 낮은 것을 섞어서 스코빌 지수를 높인다.
   그렇게 가장 작은 것이 K 이상이 될 때까지 몇 번 섞어야 하는지 구하는 문제이다.

2. 시간 복잡도 계산
   배열의 길이가 최대 1,000,000이기 때문에 섞어서 삽입할 때마다 계속해서 정렬하게 되면 시간 초과가 발생할 것이다.

3. 문제 풀이
   따라서 정렬된 상태에서 삽입, 삭제가 빈번하므로 Heap 자료구조를 떠올려야 한다.
   그 이후론 문제의 요구 조건에 따라 쉽게 구현할 수 있다.

4. 예외 사항
   애초에 모든 음식이 스코빌 지수가 K 이상인 경우와
   아무리 섞어도 K 이상으로 만들 수 없는 경우를 생각해야 한다.