<프로그래머스> 더 맵게

문제 링크

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;
    }
}