[programmers][힙Heap] Lv.2 더 맵게 (java)

 

✏️ 문제

 

 

🔢 알고리즘

 

#힙  #자료구조

 

 

🤯 풀이 방법

 

1. 자바의 힙은 PriorityQueue를 이용해서 구현한다.

2. 메소드는 offer, add, poll, peek 등 사용

3. 마지막 원소만 남았을 때 -1 출력 예외 처리 잊지 않기

4. 프로그래머스 AI가 유용하다

 

 

👾 구현 코드 (자바)

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);
        for (int num : scoville) {
            minHeap.add(num);
        }

        
        while (minHeap.size() > 1) {
            int min1 = minHeap.poll();
            if (min1 >= K) {
                return answer;
            } 
            if (minHeap.size() == 0) {
                return -1;
            }
            int min2 = minHeap.poll();
            int newN = min1 + (min2 * 2);
            minHeap.offer(newN);
            answer++;
            
        }
        if(minHeap.peek() < K) return -1;
        return answer;
    }
}