<프로그래머스> 더 맵게

문제 링크

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

문제 분석

각 음식의 스코빌 지수를 나타내는 배열과 기준이 되는 스코빌 지수(K)를 입력으로 받는다.
레오는 해당 스코빌 지수가 가장 낮은 두가지 음식을 섞어서 모든 음식이 K이상의 스코빌 지수를 가지게 하려한다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 × 2 )의 공식이 주어진다.
일단 배열에서 가장 적은 값 두가지를 뽑아내고 다시 adding하는 알고리즘을 구현해야한다.
음식을 최소로 섞어서 모든 음식이 K이상 되게하는 횟수를 리턴하는게 목표이다
만약 모든 음식들을 합친 음식의 스코빌 지수가 K보다 작으면 -1리턴한다.
Huffman Tree처럼 min-heap을 사용하기 위해 우선순위 큐에 스코빌 배열을 할당하여서 접근하는 방식이 가장 먼저 떠올랐다.
이후, while문의 peek()를 통해 음식들의 가장 적은 스코빌 지수를 체크하면서 새로운 음식을 생성해가는 동시에 카운팅을 진행하면 풀 수 있다고 생각했다.

문제 예시

(1,2,3,9,10,12) 의 스코빌 배열과 K=7이 주어진다.
스코빌 지수가 가장 낮은 두가지 음식 (1,2)를 섞어서 새로운 음식을 만든다. 그러면 (1 + 2 × 2 = 5 ) 스코빌 지수 5짜리 새로운 음식이 생성된다.(횟수 1번)
(3,5,9,10,12)에서 가장 작은 음식들을 합쳐서 새로운 음식을 만들면 3과 5를 뽑아와서 13 스코빌 지수를 가지는 음식을 생성한다.(횟수 2번)
최종적으로 (13,9,10,12) 의 배열이 생성되고 모든 음식들은 7보다 스코빌 지수가 높기 때문에 조건을 만족한다.
리턴하는 answer는 2이다.

구현 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int new_dish = 0;
        int first_dish,second_dish;
        //우선순위 큐에 스코빌 배열 새롭게 할당
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0 ;i < scoville.length; i++){
            pq.add(scoville[i]);
        }
        //가장 적은 디쉬가 K보다 작으면 while 루프 반복
        while(pq.peek() < K){
            //모든 디쉬를 다 더해도 K보다 작은경우 -1 리턴 예외처리
            if(pq.size() == 1){
                return -1;
            }
            first_dish = pq.poll();//가장 작은 첫번째 디쉬
            second_dish = pq.poll();//두번째로 작은 디쉬
            new_dish = first_dish + 2*second_dish;
            answer += 1; // 카운팅
            pq.add(new_dish);   
        }
        return answer;
    }
}