○ 문제 설명
매운 것을 좋아하는 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, 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회입니다.
○ 문제 풀이
import java.util.PriorityQueue;
class Solution {
public int solution(int[] scoville, int K) {
PriorityQueue<Integer> heap = new PriorityQueue();
int answer = 0;
for(int value : scoville){
heap.add(value);
}
while(true) {
int num1 = heap.poll();
int num2 = heap.poll();
int result = num1 + (num2 * 2);
answer++;
heap.add(result);
if(heap.peek() >= K){
break;
}
if(heap.size() == 1){
return -1;
}
}
return answer;
}
}
문제 해석을 잘못해서 전혀 엉뚱하게 풀었다가 왜 안풀리는지 시간이 지난 뒤에 알게 됐다.
먼저 scoville배열과 K에 값을 입력받는다. scoville 배열에 있는 값을 연산을 통해 K보다 커지기 위해서 몇 번 연산을 해야하는지 구하는 것이다.
문제에서 제시한 입출력 값을 예로 풀이를 하면 scoville에 0번째에 있는 값과 1번째 있는 값을 뽑아내서 아래 식을 수행한다.
int result = scoville[0] + (scoville[1] * 2);
그러면 5라는 값이 나오고 그 값을 다시 heap에 넣어준다. 이렇게 첫 번째 횟수가 끝나고 heap 안에 값을 보면 아래처럼 값이 들어있다.
아직 모든 값이 K보다 큰 것은 아니므로 위에서 했던 과정을 반복하면 아래처럼 결과가 나온다.
자, 이제 배열의 값을 보면 K의 값(= 7)보다 큰 것을 알 수 있고 두 번의 횟수로 이 결과를 얻었으므로 횟수를 반환해주면 된다.
'문제풀이 > 프로그래머스' 카테고리의 다른 글
프로그래머스. 체육복(JAVA) (0) | 2022.05.13 |
---|---|
프로그래머스. 크레인 인형뽑기 게임(JAVA)(스택) (0) | 2022.05.02 |
프로그래머스. 모의고사(JAVA)(완전 탐색) (0) | 2022.04.21 |
프로그래머스. 기능개발(JAVA)(스택/큐) (0) | 2022.04.19 |
프로그래머스 [카카오 인턴] 키패드 누르기 (Level 1)(JAVA) (0) | 2022.04.13 |