[프로그래머스|JAVA] 더 맵게 | 💡 우선순위 큐 활용 | Min Heap

[문제 링크]

프로그래머스

[문제]

 

---

 

📍 [코드]

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 자동 오름차순 (Min Heap)
        for (int s : scoville) pq.add(s);
       
        while(pq.size() > 1 && pq.peek() < K){
            int first = pq.poll();
            int second = pq.poll();
            int newSco = first + (second * 2);
            
            pq.add(newSco);
            cnt++;
        }
    
        return pq.peek() < K ? -1 : cnt;
    }
}

 

💡 접근법

• 우선순위 큐를 활용하여 자동으로 오름차순으로 정렬되도록 한다.
• 배열의 값 큐에 넣어 정렬하고
• 큐가 비어있지 않고, 제일 위의 값이 K보다 작을 때 반복문을 반복하며 횟수를 측정한다.
  • 큐의 제일 처음 값을 삭제하며 first에 저장하고,
  • 삭제한 후의 제일 처음 값을 삭제하며 second에 저장
  • 이후, 문제에 나온 조건대로 2를 곱하고 더하여 새로운 값 생성
  • 새로운 값을 큐에 넣어 자동으로 정렬되도록 한다. 
• 반복문이 끝난 후, 모든 값이 K이상이어야 하므로 제일 첫 값이 K보다 작다면 -1 반환

✅ 우선순위 큐 사용

✅ peek()→ 값 꺼내지 ❌ 보기만 / poll() → 값 꺼냄 ⭕️

 

---

 

💬 마무리

우선순위 큐가 자동으로 정렬을 해줘서 편한 것 같다.
이 문제는 우선순위 큐를 안다면 크게 어렵지 않은 문제인 것 같다.