Table of contents
더 맵게
프로그래머스섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
각 요소가 음식의 스코빌 지수를 의미하는 배열 scoville과 원하는 스코빌 지수 K가 주어졌을 때, 모든 음식의 스코빌 지수가 K 이상인 경우가 될 때까지 음식을 섞는 회수를 구하는 문제이다.
가장 작은 값과, 그 다음 작은 값을 이용하기 때문에 최소힙을 이용하면 쉽게 풀 수 있다. 자바에서는 우선순위큐 PriorityQueue를 사용한다. 우선순위가 높은 요소가 가장 먼저 출력되는 자료구조이다. Integer는 Comparable이며 디폴트로 작은 값이 높은 우선순위를 갖는다.
private int scoville(int[] scoville, int K) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i : scoville) queue.add(i);
int count = 0;
while(queue.size() > 1 && queue.peek() < K) {
int weakHot = queue.poll();
int secondWeakHot = queue.poll();
int mixHot = weakHot + (secondWeakHot * 2);
queue.add(mixHot);
count++;
}
if (queue.size() <= 1 && queue.peek() < K) return -1;
return count;
}
- scoville 배열의 모든 요소를 우선순위큐에 넣는다.
- 두개의 요소를 꺼내서 mix한 뒤 다시 큐에 넣는다.
- 섞은 횟수를 증가시킨다.
- 만약, 우선순위큐에 요소가 하나 남은 상태에서 해당 요소가 K보다 작은 경우 -1을 반환한다.
- 큐에 요소가 하나라면 섞을 수 있는 모든 요소를 다 섞었다는 의미이다.
- 그렇지 않다면 모든 요소가 K 이상의 맵기를 가졌다는 의미이므로 성공, 섞은 횟수를 반환한다.