🔥[99클럽 코테 스터디] 9일차 TIL - 더 맵게

⏳문제

문제 설명

매운 것을 좋아하는 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. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

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

---

✏️풀이

첫 번째 시도

이렇게 여러 요소들 중에서 최솟값이나 최댓값을 활용해야 하는 문제는 힙(Heap)을 활용하면 쉽게 접근할 수 있겠다는 생각이 들었다. 이번에는 최솟값을 K랑 비교해야 하기 때문에 최소힙을 사용하기로 했다.

힙에 대한 개념은 알고 있었으나, 실제로 문제에 적용해 본 경험은 없어서 문법 같은 경우에는 검색을 해서 문제를 풀었다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> scvHeap = new PriorityQueue<>();
        int count = 0;
        
        for (int i = 0; i < scoville.length; i++) {
            scvHeap.add(scoville[i]);
        }
        
        while (scvHeap.peek() < K) {
            int a = scvHeap.poll();
            int b = scvHeap.poll();
            scvHeap.add(a + b * 2);
            count++;
        }
        
        if (count == 0) {
            count = -1;
        }
        
        return count;
    }
}

우선, scoville의 모든 요소를 최소힙에 넣어주었다.
그리고, peek()함수로 루트 노드의 값(최솟값)을 확인해 K값과 비교해서 K보다 큰 스코빌 지수가 될 때까지 음식을 섞는 과정을 반복하도록 해주었다.

음식을 섞기 위해서 스코빌 지수가 가장 낮은 음식 즉, 루트 노드의 값을 먼저 추출하고,
스코빌 지수가 두 번째로 낮은 음식을 연달아 추출해 a와 b에 각각 넣어주었다.

그리고 문제에 제시된 방법에 따라 a와 b를 조합한 후, 다시 힙에 넣어주었다.
최종 반환해야 하는 값은 음식을 섞은 횟수이기 때문에, count변수에 1을 더해주었다.

마지막으로 문제 제한 사항에 "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다."라는 부분을 고려하기 위해 count가 0인 경우 즉, 음식을 섞지 않는 경우에는 -1을 count에 저장되도록 하였다.

그랬더니 몇몇 테스트 케이스에서 실패가 발생하였다..!

두 번째 시도

알고 보니, 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우를 처리하는 방법에 문제가 있었다.

스코빌 지수가 K보다 작은 요소가 2개 남아 있고, 두 요소를 조합해도 K보다 작은 경우, -1이 반환되어야 하는데,
내가 짠 코드에서는 그대로 while문을 다시 호출해버리고, 요소가 한 개 뿐인데 두 개를 추출하려고 하니 런타임 에러까지 발생해버리는 것이었다!

🖥️최종 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> scvHeap = new PriorityQueue<>();
        int count = 0;
        
        for (int i = 0; i < scoville.length; i++) {
            scvHeap.add(scoville[i]);
        }
        
        while (!scvHeap.isEmpty() && scvHeap.peek() < K) {
            int a = scvHeap.poll();
            
            if (!scvHeap.isEmpty()) {
                int b = scvHeap.poll();
                scvHeap.add(a + b * 2);
                count++;
            }
            else {
                count = -1;
            }
        }
        return count;
    }
}

그래서 while 조건에 힙이 비어있지 않다는 조건을 추가해 주었고, 남아 있는 요소의 갯수가 2개 이상인 경우에만 음식을 섞도록 조건문을 추가해 주었다. 이렇게 처리함으로써, 만약 요소가 한 개 뿐인 상황에서는 count에 -1이 저장되도록 구현할 수 있었다😎

---

🔗문제 링크
💻Repository