[프로그래머스 Lv.2] 더 맵게(Java)

➕ 문제 설명

주어진 배열 scoville의 모든 원소가 특정 K 이상이 되도록 섞는 과정을 반복

음식을 섞는 방법

• 가장 맵지 않은 두 개의 음식
• 새로운 스코빌 지수 = 가장 작은 값 + 두번째로 작은 값 * 2

🔍 모든 음식의 스코빌 지수가 K 이상이 되는 최소 횟수를 구하라

     불가능하다면 -1 반환

---

 

📖 문제 풀이 과정

 

우선순위 큐(Heap) 사용

스코빌 지수를 최소한으로 섞어야 하므로
항상 가장 작은 두 개의 스코빌 지수를 효율적으로 꺼낼 수 있는
최소 힙이 적합함

PriorityQueue<Integer> heap = new PriorityQueue<>();

 

• 스크빌 지수를 힙에 넣는다.
• 가장 작은 두 값을 꺼내 새로운 값을 계산하고 다시 힙에 넣는다.
• 위 과정을 반복하며 카운트를 증가한다.
• 모든 스코빌 지수가 K 이상이 되면 횟수를 반환, 그렇지 않으면 -1 반환

 

---

 

😎 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        // PriorityQueue를 활용한 최소 힙 생성
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        // 배열의 모든 요소를 힙에 삽입
        for (int s : scoville) {
            heap.add(s);
        }
        
        int count = 0; // 섞은 횟수
        while (heap.size() > 1) { // 최소 2개 이상일 때만 섞기 가능
            int first = heap.poll(); // 가장 작은 값
            if (first >= K) { // 모든 값이 K 이상이면 종료
                return count;
            }
            
            int second = heap.poll(); // 두 번째로 작은 값
            int newScoville = first + (second * 2);
            heap.add(newScoville); // 섞은 값 힙에 삽입
            count++; // 섞은 횟수 증가
        }
        
        // 마지막 남은 값이 K 이상인지 확인
        return heap.peek() >= K ? count : -1;
    }
}

 

---

 

??? : 이거 그냥 큐로 해도 되는거 아냐?

 

큐를 사용해도 된다. 느려

하지만 여기서의 조건은 항상 가장 작은 두 개의 값을 빠르게 선택하고 계산하는 것이다.

 

(Min-Heap)

우선순위 큐는 데이터를 자동으로 정렬된 상태로 관리하며 삽입 삭제가 효율적이다.

➡️ 최소값을 빠르게 꺼내 처리할 수 있다.