[프로그래머스] 더 맵게

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   주어진 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수가 가장 낮은 두 개의 음식을 섞어 스코빌 지수를 높이는 과정을 반복하려 한다. 이때 조건을 만족하기까지의 최소 횟수를 구하는 문제이다. 섞는 방식은 다음과 같다.

 

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

 

   음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어어진다. 제한 사항은 다음과 같다.

 

• 2 ≤ scoville 배열의 길이 ≤ 1,000,000
• 0 ≤ K ≤ 1,000,000,000
• 0 ≤ scoville 원소 ≤ 1,000,000
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1 반환

---

접근 방식

   우선순위 큐의 개념을 이용해 문제를 해결하였다. 문제에서 스코빌 지수를 높이기 위해선 두 음식을 섞어야 하며, 이때 두 음식을 선정하는 기준은 스코빌 지수가 가장 낮은 첫번째, 두번째 스코빌 지수들이다. 새로 만들어진 스코빌 지수를 다시 포함하여 스코빌 지수를 높이는 과정이 다시 진행되기 때문에 스코빌 지수는 매번 오름차순으로 정렬되어야 한다.

 

   다음은 문제의 예제이다. K와 스코빌 지수가 다음과 같이 주어질 때 새로운 스코빌 지수를 구하기 위해선 스코빌 지수 1과 2를 이용해야 한다.

 

 

   1과 2를 이용해 만든 새로운 스코빌 지수는 5이며 이를 스코빌 지수에 다시 포함시킨다.

 

 

   배열에서 매번 연산에 필요한 스코빌 지수들을 하나씩 찾는 방식은 매우 비효율적이다. 따라서 힙의 구조를 이용하는 우선순위 큐에 저장하는 방식으로 바꾼다.

 

 

   우선순위 큐를 이용해 스코빌 지수에 대한 정렬과 가장 낮은 스코빌 지수를 쉽게 구할 수 있게 되었다. 가장 낮은 스코빌 지수가 K 이상이거나 스코빌 지수가 1개밖에 남지 않은 경우(K 이상인 스코빌 지수를 만들 수 없음)까지 이전 과정들을 반복한다.

 

 

   스코빌 지수의 최소값이 9이므로 K : 7인 경우를 만족하여 종료된다.

---

코드

import java.util.PriorityQueue;

public class 프로그래머스42626번 {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>();

        //우선순위 큐를 이용한 저장값 자동 정렬(default : 오름차순)
        for (int s : scoville)
            q.add(s);
        //저장된 값 중에서 가장 작은 값이 K보다 크면 종료
        //큐에 저장된 값이 1인 경우 두 음식을 섞을 수 없으므로 종료
        while (q.peek() < K && q.size() > 1)
            //두 음식을 섞어서 만든 새로운 스코빌 지수를 큐에 저장
            q.add(q.poll() + q.poll() * 2);
        //큐의 가장 작은 값이 K 이상이면 모든 음식의 스코빌 지수가 K 이상임을 만족
        //아닌 경우 K 이상의 스코빌 지수를 만들 수 없으므로 -1 반환
        return q.peek() >= K ? scoville.length - q.size() : -1;
    }
}