[프로그래머스/힙] Level 2 더 맵게 (JAVA)

문제

---

풀이

최솟값들을 가지고 계속 연산을 하고, 계속 값의 순위가 바뀌기 때문에 PriorityQueue를 사용했다.

PriorityQueue의 시간복잡도는 add, remove는 O(log(n)), retrieve는 O(1)이다.

ArrayList의 add, remove operation 시간복잡도가 O(Nlog(n))인 것에 비해 훨씬 효율적이다.

---

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int each : scoville) {
            pq.offer(each);
        }
        
        int count = 0;
        while (true) {
            if (pq.peek() >= K) {
                return count;
            }
            
            if (pq.size() == 1) {
                return -1;
            }
            
            int left = pq.poll();
            int right = pq.poll();
            pq.offer(scoville(left, right));
            count++;
        }
    }
    
    private int scoville(int left, int right) {
        return left + (right * 2);
    }
}