프로그래머스 더 맵게(Level2 Java)

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

프로그래머스

---

 

문제 설명

매운 것을 못 먹는 Leo는 모든 음식의 스코빌 지수를 K이상으로 만들고 싶어 합니다.

• 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해, 가장 지수가 낮은 두 음식을 다음과 같이 섞습니다.
• 섞은 음식의 스코빌 지수 = 가장 낮음 + (두 번째 낮음 * 2)
• 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞은 최소 횟수를 구하는 문제입니다.

---

문제 해결을 위한 과정

이 문제의 핵심은 "데이터를 추가하거나 삭제할 때마다 항상 정렬된 상태(가장 작은 값)를 유지하는 것"입니다. 이를 위해 최소 힙(Min Heap) 구조인 PriorityQueue를 사용했습니다.

---

소스코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int answer = 0;
        
        for(int i = 0; i < scoville.length; i++) {
            pq.offer(scoville[i]);
        }
        
        while(!pq.isEmpty()) {
            if(pq.size() >= 2) {
                int food1 = pq.poll();
                int food2 = pq.poll();
                
                if(food1 >= K)
                    break;
                else {
                    answer += 1;
                    int newFood = food1 + food2 * 2;
                    pq.offer(newFood);
                }
            } else {
                int food = pq.poll();
                if(food >= K)
                    break;
                else {
                    return -1;
                }
            }
        }
    
        return answer;
    }
}