프로그래머스 - 더 맵게 (힙)

220317

import java.util.*;
 
class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0; i<scoville.length; i++){
            pq.add(scoville[i]);
        }
        int answer = 0;
        
        while(pq.peek()<K){
            if(pq.size()<=1) return -1;
            int min1 = pq.poll();
            int min2 = pq.poll();
            
            answer++;
            pq.add(min1+ 2*min2);
        }
 
        return answer;
    }
}

 

 

 

우선순위큐 쓰면 쉬움

 

    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        for (int s : scoville)
            pq.add(s);
 
        int a, b;
 
        while (pq.size() > 1) {
            // System.out.println("피큐픽" +pq.peek());
            if (pq.peek() >= K)
                return answer;
            a = pq.poll();
            b = pq.poll();
            // System.out.println(a+" "+b);
            pq.add(a + 2 * b);
            answer++;
        }
        if (pq.isEmpty())
            return -1;
        if (pq.peek() >= K)
            return answer;
        else
            return -1;
 
    }