프로그래머스 - 더 맵게 (Java, 자바)

문제 링크

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

---

문제 풀이 과정

스코빌 지수가 낮은 항목에 대해서 계산이 이루어 지기 때문에 처음에는 배열을 이용해서 정렬후 진행 하면 되겠다 라고 생각했다.
하지만 배열을 이용하면 Index 관리에 어려움이 있을 것 같다는 생각을 했다.

항상 숫자가 정렬되어 있고 낮은 수 먼저 꺼낼 수 있는 우선순위큐를 사용했더니 금방 풀이가 되었다.

주어진 배열을 우선순위 큐에 넣으면 이런 구조가 된다.
이때 제일 먼저 나가는 값은 가장 작은 값이 된다.

이 문제의 핵심은 가장 작은 숫자가 K 이상이면 되는 것이다.
그래서 반복문을 통해서 작은 숫자가 K 이상일때까지 반복하였다.

우선순위큐에서 poll을 두번 하면 첫번째 값은 가장 작은 값이며, 그 다음은 두번째로 작은 수이다.
이 두 수를 계산 후 다시 우선순위큐에 넣으면 위와 같은 구조가 된다.

그다음 이 구조에서 가장 작은 수가 K가 넘지 않으면 다시 반복을 한다.

같은 방식으로 한번 더 진행 하면 위와 같은 구조가 된다.
이때 가장 작은 수가 K 이상이 되므로 반복문이 종료 된다.

여기서 주의 할 점은 우선순위큐의 크기가 2이상일때만 계산이 진행 되어야 한다.
만약 가장 작은 수가 K 이상이 안되어 계산을 한번 더 진행 되어야 하는데 우선순위큐 크기가 2보다 작으면 계산이 불가 하기 때문에 -1을 리턴하고 종료 해야 한다.

---

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int a : scoville){
            pq.add(a);
        }

        int min = pq.peek();
        while (min < K){
            if(pq.size() >= 2){
                pq.add(pq.poll() + (pq.poll() * 2));
                min = pq.peek();
                answer++;
            }
            else{
                return -1;
            }
        }

        return answer;
    }
}