[프로그래머스] 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

우선순위 큐를 활용하여 해결 가능한 문제이며, Java 의 경우에는 PriorityQueue 를 사용하여 코드를 작성하였습니다.

최대 계산 가능한 loop 횟수는 scoville 배열 원소 개수 - 1 개 이며, 우선순위 큐의 (첫번째 원소 + (두번째 원소 * 2)) 값을 계산하여 다시 우선순위 큐에 넣고 모든 원소가 K 값보다 클 경우에 count 를 계산하는 것이 이 문제의 목적입니다.

 

(예제 코드)

import java.util.*;
class Solution {
    public static int solution(int[] scoville, int K) {
        int answer = -1;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int elem : scoville) {
            pq.add(elem);
        }
        for (int i = 0; i < scoville.length-1; i++) {
            int first = pq.poll();
            int second = pq.poll();
            pq.add(first + (second * 2));
            if (pq.peek() >= K) {
                return i+1;
            }
        }
        return answer;
    }

}