[프로그래머스] 42626. 더 맵게

문제 링크

[프로그래머스] 42626. 더 맵게

풀이 과정

우선순위 큐로 힙을 구현했습니다. 우선순위 큐에 남아있는 음식들로 더이상 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우를 주의해서 코드를 구현해야 합니다.

아래 코드에서 while 문 안의 두 개의 if 문은 다음과 같은 의미를 가집니다.

우선순위 큐의 맨 앞 요소의 스코빌 지수가 K 이상인데, 큐에 남아있는 음식이 하나밖에 없을 때는 더이상 진행할 수 없으므로 -1을 리턴합니다.

코드

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    public static int solution(int[] scoville, int K) {
        int answer = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for (int sco : scoville)
            pq.add(sco);

        boolean flag = true;

        while (true) {
            if (pq.peek() >= K) {
                break;
            }

            if (pq.size() == 1) {
                flag = false;
                break;
            }

            int a = pq.poll();
            int b = pq.poll();

            pq.add(a + b * 2);
            answer++;
        }

        return flag ? answer : -1;
    }

    public static void main(String[] args) {
        int[] scoville = {1, 2, 3, 9, 10, 12};
        int K = 7;

        solution(scoville, K);
    }
}