문제 설명
매운 것을 좋아하는 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 합니다.
입출력 예
| scoville | K | 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회입니다.
문제를 처음엔 잘못이해해서, 가장 낮은 스코빌 지수의 음식과 두번째로 낮은 스코빌 음식을 섞고, 두번째로 낮은 스코빌 음식은 그대로 배열에 살려두는 것인 줄 알았으나, 그렇지 않았다.
문제를 푸는 것이 그다지 어렵지 않았으며, 다만 PriorityQueue 라이브러리를 이용하니 어렵지 않았다.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();이렇게 선언하고,
minHeap.poll(); //최상단 노드의 값을 꺼낸다.(꺼내고 큐에서 값이 사라진다.)
minHeap.peek(); //최상단 노드를 읽어온다.(읽어오기만함. 꺼내지는 않는다. 따라서 큐에 값이 살아있다.)
minHeap.remove(); //최상단 노드를 제거한다.(큐에서 노드가 사라진다.)
minHeap.size(); //힙의 사이즈를 리턴.
minHeap.toArray(); //큐의 값들을 배열화한다.(값을 print하기위해 사용했다. **다만,정렬된 순서대로 배열화되지는 않는다!!)크게 이정도의 정보를 갖고 시작했다.
for (int i: scoville ) {
minHeap.add(i);
}힙에 스코빌 배열 값들을 차례로 넣어준다.
넣어준 것 만으로 알아서 최소값 우선순위큐대로 정렬되어 Root노드에 최소값이 들어간다.
while (minHeap.peek() < k) {
if (minHeap.size() == 1) return -1;
int temp = minHeap.poll() + (minHeap.poll() * 2);
minHeap.add(temp);
++answer;
}여기가 핵심 솔루션 부분인데 고민하는데 30분이 걸렸던 것 같은데 다 짜고보니 6줄이다.
결국 문제를 해석해서 어떤 로직을 구현하면 되는지 글로 써보면
우선순위큐에 이미 최소값이 Root에 있기에 최소값을 가져오게되고,
스코빌 최소값이 k값인 7보다 작다면,
1번째낮은 + 2번째낮은*2, 한 값을 넣어주고 1번째낮은,2번째낮은 값을 삭제하면된다.
int temp = minHeap.poll() + (minHeap.poll() * 2);
minHeap.add(temp);
++answer;위에 1,2 값이 사라지고 5 값이 들어가는 것이다.
[5,3,9,10,12]
이런식으로
결국 위 배열도 최소값 우선순위큐에 넣으면 3이 Root값으로 나오기 때문에 일일이 for문돌려가며 혹은 Sorting할 필요 없이 그냥 쓰면된다는 걸 느끼는게 가장 중요한 핵심인 듯하다.
그리고
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.이 부분을 어떻게 구현해야하나 정말 고민을 많이 했는데..
스코빌지수를 K 이상으로 만들 수 없는 경우가 어떤 경우가 있는지 도저히 생각이 안나더라
- 스코빌 배열이 1개인 경우
- 두번째 낮은 스코빌 값을 더해줘야하는데 존재하지 않기에 값이 유지되어 높아지지 않게되고, K 이상으로 만들 수 없음
- 0 값을 2개 갖고있는 경우..?
- [0,0,1,2,3] 이런 경우는 두번째로 낮은 스코빌의 값이 0이 두개니까 스코빌을 높일 수 없는게 아닐까 했지만, 0이 두개인 것은 두번째로 낮은 숫자가 아니라 같은 값이기에 아닌것인가보다.
- disregard
