[프로그래머스] 더 맵게

문제

 

 

접근 방식

가장 낮은 값과 (다음으로 낮은 값 * 2)을 더한 값을 다시 포함하여

모든 수가 K 이상이 되게 만들어야 한다.

 

즉, 가장 낮은 값 두 개를 뺀 후에 섞고 다시 섞은 것을 추가해야 하고

이 때, 항상 정렬된 상태를 유지해야 하는게 중요하다.

 

섞은 것을 추가할 때마다 정렬을 하기에는 시간 복잡도가 비효율적이기 때문에

값이 추가되어도 항상 정렬된 상태를 유지할 수 있는 우선순위 큐를 사용하면 쉽다.

 

처음에는 우선순위 큐에 모든 값들을 넣어주고

큐에서 가장 작은 값을 두 개씩 빼가며 섞어주고 다시 넣어주다가

꺼낸 값이 K 이상이라면 이후의 값들도 당연히 K 이상이기 때문에

현재까지의 카운트를 리턴해주면 되고

값을 하나 꺼냈는데 더 이상 남은 것이 없다면 더 이상 섞을 것이 없기 때문에

모든 값을 K 이상으로 만들 수 없다는 것이 되어 -1을 출력해준다.

 

 

풀이

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        
        for (int s : scoville) q.offer(s);
        
        int cnt = 0;
        
        while(!q.isEmpty()) {
            int first = q.poll();
            
            if(first >= K) break;
            if(q.isEmpty()) return -1;
            
            cnt++;
            
            q.offer(first + (q.poll() * 2));
        }
        
        return cnt;
    }
}