더 맵게

---

🔗 🔗 더 맵게

문제 설명

---

매운 것을 좋아하는 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 합니다.

입출력 예

---

입출력 예 설명

---

스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5

가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13

가진 음식의 스코빌 지수 = [13, 9, 10, 12]

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

풀이

---

문제 자체는 간단하다. scoville 중 가장 작은 값과 두 번째로 작은 값을 호출하여 섞는다. 이 과정을 수행하여 모든 요소의 값이 K 이상이 될 때까지 반복한다.

만약, 모든 연산을 수행했음에도 K 이상이 되지 못 하는 음식이 있을 경우 -1을 반환한다.

뽑아야 하는 요소의 법칙이 정해져 있으므로 조합은 맞지 않다.

1. 데이터를 호출할 때마다 가장 작은 값이 나와야 한다.
2. 데이터의 삽입, 삭제가 자유롭다.

얼핏 보면 ArrayList 사용해서 정렬하면 되지 않을까? 싶지만 이 방법은 효율성이 극히 떨어진다. 연산을 수행할 때마다 ArrayList의 정렬 과정이 필요하기 때문.

이 문제는 PriorityQueue 객체를 알고 있다면 쉽게 풀 수 있고, 아니라면 고생 좀 하게 되는 문제다.

PriorityQueue는 이름 그대로 큐지만, 일반적인 LIFO 방식이 아니다. PriorityQueue의 독특한 규칙은 아래와 같다.

1. 데이터의 우선순위를 파악하여 가장 높은 우선순위의 데이터를 먼저 출력
2. 이진트리 방식을 사용하으로 시간복잡도는 $O(N\log{N})$
3. 베이스는 Queue를 따른다.

PriorityQueue의 특징은 이 문제와 매우 적합하다. 각 요소가 숫자로 이루어져 있으므로, 가장 낮은 숫자를 우선순위로 지정하여 데이터를 출력하면, 굳이 정렬을 사용하지 않고도 가장 작은 데이터를 호출할 수 있을 것이다.

JAVA
1
2
3
4
5
// 우선순위가 낮은 순
PriorityQueue<Integer> queue = new PriorityQueue<>();

// 우선순위가 높은 순
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue를 선언할 때, 우선순위를 지정할 수 있다.

이 문제는 가장 작은 수를 최우선으로 뽑아야 하므로, 우선순위가 낮은 순으로 뽑는 것이 적절할 것이다.

PriorityQueue에서 뽑은 요소가 K를 넘지 않을 경우, 아직 덜 매운 음식이 있으므로 연산을 수행한다.

K를 넘는다면, 가장 안 매운 음식도 K를 넘으므로 연산을 수행할 필요가 없다.

코드

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * 더 맵게 클래스
 *
 * @author RWB
 * @since 2021.12.27 Mon 13:43:34
 */
class Solution
{
	/**
	 * 해답 반환 메서드
	 *
	 * @param scoville: [int[]] 음식의 스코빌 지수 배열
	 * @param K: [int] 목표 스코빌 지수
	 *
	 * @return [int] 해답
	 */
	public int solution(int[] scoville, int K)
	{
		int answer;
		
		// 섞을 요소가 부족할 경우
		if (scoville.length < 2)
		{
			answer = -1;
		}
		
		// 섞을 요소가 충분할 경우
		else
		{
			PriorityQueue<Integer> queue = new PriorityQueue<>();
			
			answer = 0;
			
			for (int item : scoville)
			{
				queue.add(item);
			}
			
			while (Objects.requireNonNull(queue.peek()) < K)
			{
				// 섞을 요소가 부족할 경우
				if (queue.size() < 2)
				{
					answer = -1;
					
					break;
				}
				
				queue.add(Objects.requireNonNull(queue.poll()) + (Objects.requireNonNull(queue.poll()) * 2));
				
				answer++;
			}
		}
		
		return answer;
	}
}

queue.poll(), queue.peek()이 null을 반환할 가능성이 있으므로, Objects.requireNonNull()를 사용하여 관련 오류를 제거한다.

Objects.requireNonNull()가 없어도 동작에 영향은 없다.