더 맵게

[문제 접근법]

- 최소 힙을 만들어서(우선순위 큐 사용) 최솟값을 하나씩 우선순위 큐에서 꺼낸다.

가장 맵지않은 음식이 K보다 적으면 그림 1처럼 두 번째로 맵지 않은 음식과 섞는다.

그리고 아래 연산을 한 후 다시 최소 힙에 넣는다. 

 

만약 최소 힙의 가장 맵지 않은 음식의 스코빌 값이 K 이상이면 return 하여 끝낸다.

 

그림 1- 스코빌 지수

 

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

코딩테스트 연습 - 더 맵게

---

[구현 1] 

1. 최소 힙(우선순위 큐)을 만든다

2. 힙에서 하나씩 꺼내 가장 맵지 않은 음식이 스코빌 지수기 K이상인지 확인한다.

3. 스코빌 지수보다 적으면 두 번째로 맵지 않은 음식을 꺼내 음식을 섞는다. 섞은 후 큐에 넣는다

4. 2,3번을 반복 중 가장 맵지 않은 음식이 스코빌 지수보다 크거나 같으면 반복은 종료한다.

5. 모든 음식을 K이상 못 만들면 -1을 리턴한다.

 

package com.codingtest.programmers.level2;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.PriorityQueue;

//더 맵게
public class MoreSpicy {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();    //1.최소 힙 생성

        for (Integer scovil : scoville)
            pq.add(scovil);

        while (!pq.isEmpty() || pq.size() > 1) {
            Integer first = pq.poll();

            if (first < K) {                    //2. 가장 맵지 않은 음식의 스코빌 지수 확인
                if (pq.isEmpty()) return -1;    //5. 모든 음식을 스코빌 지수를 K이상으로 못만드는 경우

                else {                          //3. 스코빌 지수보다 적으면 2번 째로 맵지 않은 음식이랑 섞는다
                    Integer second = pq.poll();
                    pq.add(second * 2 + first);
                    answer++;
                }
            }
            else break;                         //4. 가장 맵지 않음 음식의 스코빌 지수가 K 이상이면 종료한다
        }

        return answer;
    }

    public static void main(String[] args) {
        int[] scoville = {1, 2, 3, 9, 10, 12};
        int k = 10000;
        MoreSpicy ms = new MoreSpicy();
        int solution = ms.solution(scoville, k);

        System.out.println("solution = " + solution);
    }
}