[프로그래머스] 더 맵게 - Java

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

 

문제 설명

---

문제 풀이

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> list = new PriorityQueue<>();
                
        for (int i : scoville) {
			list.offer(i);
		}
       
        while(list.peek() < K) {
        	if (list.size() == 1) return -1;
        	
        	int s1 = list.poll();
        	int s2 = list.poll();
        	
        	list.offer(s1 + s2 * 2);
        	
        	answer++;
        }
        
        return answer;
    }
}

list로 풀게 되면 자료 추가 후 매번 오름차순 정렬을 해야하기 때문에 시간 초과

->

min heap 을 사용해서 항상 자료가 최소값 기준으로 정렬되어 있도록 함

자바에서 min heap 은 PriorityQueue로 구현