[Algorithm] 프로그래머스 더 맵게

코딩테스트 연습 - 더 맵게

 

풀이

1. 스코빌지수는 항상 오름차순으로 관리되어야 한다. (PriorityQueue 사용)

2. 가장 낮은 스코빌 지수가 K보다 작을 경우 로직을 수행한다.

3. pq에서 가장 낮은 지수와 그 다음 낮은 지수를 꺼내 연산 후 다시 넣는다.

4. pq에 1개의 지수만 남았는데도 K보다 작을 경우 더 이상 수행이 불가능한 것으로 판단해 -1을 리턴해 종료시킨다.

 

전체 소스코드

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) {
            int one = pq.poll();
            int two = pq.poll();
            pq.offer(one + (two * 2));
            answer++;
            
            if (pq.size() == 1 && pq.peek() < K) return -1;
        }
        
        return answer;
    }
}