[プログラマー]もっと辛い(Java)

🔗 質問リンク

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

👨🏻‍💻 初回作成コード(実行時エラー)

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int temp1;
        int temp2;
        
        List<Integer> list = new LinkedList<>();
        
        for (int i: scoville)
            list.add(i);
        
        Collections.sort(list);
        
        while ((list.get(0) < K) || (list.get(1) < K)) {
            temp1 = list.remove(0);
            temp2 = list.remove(0);
            list.add(0, temp1 + (temp2*2));
            answer++;
        }
        
        if(list.get(0) < K)
            return -1;
        
        return answer;
    }
    
}

👨🏻‍💻 PriorityQueueで作成されたコード

import java.util.*;

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

📝 n/a.結論

この問題はheapを用いて解決した問題である.
最初はLinkedList classを使用して問題を解決しようとしたが、論理は正しいが、コード効率が低下したため、採点時にすべての問題にランタイムエラーが発生した.
そこで,実行時間を短縮するために,heap構造の自動ソートとして内部構造を用いたPriorityQueueを用いて問題を解決する.
PriorityQueueの内部構造はHeap構造で構成されているため,時間的複雑度はO(NLOGN)であり,今回の問題と同様にHeapを用いて解決する必要がある問題に非常に適している.