[프로그래머스] 더 맵게(JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=java

---

풀이

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.size() >= 2){
            int first = pq.poll();
            if(first < K){
                answer++;
                int second = pq.poll();
                pq.add(first + second*2);
            }else{
                pq.add(first);
                break;
            }
        }
        if(pq.size() == 1){
            int first = pq.poll();
            if(first < K){
                return -1;
            }
        } 
        
        return answer;
    
    }
}

 

우선순위 큐로 오름차순 정렬을 한 것을 앞에서부터 뽑아 생각한다.

만약 큐 사이즈가 2이상(두개를 뽑아야 할 수 있기 때문에)라면 반복을 하면서 비교한다.

1. 처음 뽑은 값이 K보다 작다면 조건을 만족하지 못한다.

1-1. answer++을 통해 횟수가 진행 되었음을 표시하고, 두번째 값을 꺼내어 연산을 진행한 뒤에 더한다.

2. 만약 뽑은 값이 K보다 크거나 같다면 더 이상 반복할 필요가 없으므로 큐에 원래 값을 다시 넣어주고 반복을 종료하낟.

3. 최종적으로 큐 사이즈가 1이면 마지막(큐사이즈가 2인 반복)에 처리된 값을 검사하기 위해 하나만 뽑아서 검사한 뒤에 만약 K보다 작다면 -1을 반환함으로써 예외처리를 한다.