[프로그래머스] 42626번 : 더 맵게

코드

import java.util.PriorityQueue;

public class PRO_42626 {
    public static int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i : scoville) pq.add(i);

        int answer = 0;
        while (pq.size() > 1) {
            int first = pq.poll();
            int second = pq.poll();

            if (K <= first) return answer;

            int temp = first + second * 2;
            ++answer;

            pq.add(temp);
        }

        if (pq.poll() < K) return -1;
        return answer;
    }

    public static void main(String[] args) {
        int[] scoville = {1, 2, 3, 9, 10, 12};
        int K = 7;

        System.out.println(solution(scoville, K));
    }
}

풀이 및 느낀점

우선순위큐에 값들을 저장하면 자동으로 값들이 오름차순으로 정렬된다. 이 원리를 이용하여 문제에 접근했다. pq에 저장된 첫번째 값과 두번째 값은 저장된 값 들 중에서 제일 작은 값들이다. pq 내의 첫번째 값과 두번째 값을 꺼내서 스코빌 지수를 만들었고 answer를 증가시킨다. 그리고 만들어진 스코빌지수를 pq에 저장하면 자동으로 오름차순 정렬이 된다. 이를 반복하다보면 pq의 크기가 1이 되는 순간이 있는데 이때 반복문을 빠져나가고, pq에 1개 저장되어 있는 값이 최소 스코빌 지수(k)보다 작다면 -1을 리턴해주고 그렇지 않다면 answer를 출력한다.

참고자료