[Programmers] 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

문제 설명

힙 자료구조를 사용하면 간단하게 해결할 수 있다. 힙은 최솟값 또는 최댓값을 효율적으로 탐색할 수 있는 자료구조이다. 이 문제의 경우 모든 음식의 스코빌 지수를 K 이상으로 높여야 한다. 그렇기 때문에 최소 힙을 사용하여 힙을 peek한 값이 K 이상이 되도록 만들면 된다. 자바에서는 PriorityQueue를 힙의 구현체로 사용할 수 있다.

코드

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        for (int elem: scoville) {
            heap.add(elem);
        }
        
        int count = 0;
        while (heap.size() > 1 && heap.peek() < K) {
            int newScoville = heap.poll() + heap.poll() * 2;
            heap.add(newScoville);
            count++;
        }
        
        if (heap.size() == 1 && heap.peek() < K) {
            count = -1;
        }
        
        return count;
    }
}