알고리즘 문제 풀이를 블로그에 올리는 이유는 풀이, 코드를 기록하기 위함이니
앞으로 문제를 다 긁어오기보다 링크만 두고 풀이가 잘 보이도록 포스팅 할 예정입니다!

📄 문제

[프로그래머스] 더맵게

---

👩‍💻 풀이

1. 문제 이해

이 문제는 주어진 음식 스코빌 지수 값들 중
가장 작은 값 두 개를 결합하여 새로운 음식을 만들고
이를 반복하여 모든 음식이 최소 스코빌 지수를 넘도록할 때
필요한 최소 반복 횟수를 구하는 문제이다.

2. 풀이

• 우선순위 큐에 값을 넣어 작은 수가 앞에 오도록 정렬
• 가장 작은 값을 peek하여, 그 값이 K 보다 작다면
  - 가장 작은 두 값을 뽑아 새로운 음식 조합
  - 해당 음식을 다시 food에 추가하고 조합 횟수인 cnt++
  - 두 개의 음식을 뽑은 후, food가 비었고, 새로 조합한 음식의 스코빌 지수도 K보다 낮다면 문제의 조건을 만족할 수 없는 케이스이므로 -1 반환

import java.util.PriorityQueue;

public class Solution {

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

        System.out.println(solution(scoville, K));
    }

    public static int solution(int[] scoville, int K) {

        PriorityQueue<Integer> foods = new PriorityQueue<>();
        for(int s : scoville) {
            foods.add(s);
        }

        int cnt = 0;

        while(foods.peek() < K) {
            int f1 = foods.poll();
            int f2 = foods.poll();
            int newFood = f1 + (f2 * 2);

            if(foods.isEmpty() && newFood < K) {
                return -1;
            }

            foods.add(newFood);
            cnt++;
        }

        return cnt;
    }
}