문제 바로가기

접근방식

처음에는 리스트에다 옮겨서 오름차순 sort하고 0번째,2번째 get으로 계산하고 remove로 없애고 반복시켰는데 모두 효율성 테스트에서 실패했다.
AI코드 피드백?을 사용해봤는데 우선순위큐를 사용하란다

틀린 첫번째 코드

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        List<Integer> list=new ArrayList<>();
        
        for(int i:scoville){
            list.add(i);
        }
        
        while(true){
            if(allKup(K,list)) break;
            Collections.sort(list);
            int res=list.get(0)+(list.get(1)*2);
            list.remove(0);
            list.remove(0);
            list.add(res);
            //System.out.println(list);
            answer++;
        }
        return answer;
    }
    
    static boolean allKup(int k, List<Integer> list){
        for(int i:list){
            if(i<k) return false;
        }
        return true;
    }
}

정답코드(우선순위큐)

import java.io.*;
import java.util.*;

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

우선순위큐는 하도 많이 써봐서 쉽지...
리스트에서 sort랑 모두 k이상인지 확인하는게 시간이 많이 걸리긴 하나보다