프로그래머스 문제풀이 - 더 맵게
매운 것을 좋아하는 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 합니다.
입출력 예
scovilleKreturn
| [1, 2, 3, 9, 10, 12] | 7 | 2 |
입출력 예 설명
-
스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12] -
스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]
모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.
PriorityQueue(우선순위 큐) 를 사용하여 푸는 문제였다.
우선순위 큐는 먼저 들어간 데이터가 나오는 일반적인 큐와는 다르게
데이터를 꺼내는 우선순위가 가장 높은 데이터가 먼저 나온다.
객체를 제네릭스에 우선순위 큐에 add 하기 위해서는 해당 객체의 클래스에
Comparable를 구현해야 우선순위를 측정할수 있다.
Java는 기본적으로 낮은 숫자부터 큰 숫자까지 오름차순으로 정렬한다.
PriorityQueue는 add, offer로 큐에 요소들을 추가할수 있고 poll로 우선순위가 가장 높은데이터를 추출한다.
int answer = 0;
int first = 0;
int second = 0;
int newItem = 0;
1. 필요한 변수들과 PriorityQueue를 선언한다.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
2. 받아온 매개변수 배열을 앞에서 선언한 priorityQueue에 add한다.
for(int i : scoville) {
priorityQueue.add(i) }
3. 스코빌 지수가 K 이상인 값들만 우선순위 큐에 있도록 반복한다.
while(priorityQueue.size() > 1) {
if(priorityQueue.element() > K) { break;}
else {
first = priorityQueue.poll();
second = priorityQueue.poll();
newItem = first + (second * 2);
priorityQueue.add(newItem);
answer += 1;
}
4. 큐의 값이 1개밖에 없는데 이 값이 K보다 크지 않을 경우 -1을 반환한다.
if(priorityQueue.size() <=1 && priorityQueue.element() < K) {
answer = -1;
}
return answer;