[프로그래머스] 더 맵게

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<scoville.length; i++){
            list.add(scoville[i]);
        }
        Collections.sort(list);
        while(list.get(0)<K){
            if(list.size()==1 && list.get(0)<K){
                answer = -1;
                break;
            }
            int num1 = list.get(0);
            int num2 = list.get(1);
            
            list.remove(0);
            list.remove(0);
            
            list.add(num1 + (num2*2));
            
            Collections.sort(list);
            
            answer++;
        }
        return answer;
    }
    
}

효율성 테스트 통과 못함

 

import java.util.*;

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

우선순위 큐를 이용하면 정렬을 하지 않아도 되므로 시간을 아낄 수 있는 것 같다.

효율성 테스트 통과 

 

2번째 시도 풀이

import java.util.*;

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

첫번째와 비슷하지만, pq.poll()이 값을 반환해준다음 삭제된다는 것을 이용하여 코드가 아주 조금 줄었다. 

배열에서 최소값 또는 최대값을 찾고, 꺼내어서 배열이 계속해서 변화하는 로직에서는 for문을 통해 풀기 어렵다.

이럴때, PriorityQueue를 사용하면 쉽게 풀 수 있는 것 같다.