[LeetCode-875] 파라메트릭 서치 첫 문제 - 답이 될 후보값을 이진 탐색한다

• 문제 링크: https://leetcode.com/problems/koko-eating-bananas/
• 파일 경로: src/main/java/coding_test/이진탐색/LC0875_KokoEatingBananas.java
• 난이도: Medium

문제 설명

바나나 더미가 n개 있고, i번째 더미에는 piles[i]개의 바나나가 있다. h시간 안에 모든 바나나를 다 먹어야 한다. 매 시간 한 더미를 골라 속도 k만큼 먹는데(더미에 k개보다 적게 남았으면 그 시간엔 그 더미만 다 먹고 끝), 모든 바나나를 h시간 안에 다 먹을 수 있는 최소 속도 k를 구한다.

Input: piles = [3,6,7,11], h = 8   -> Output: 4
Input: piles = [30,11,23,4,16], h = 5  -> Output: 30
Input: piles = [30,11,23,4,16], h = 6  -> Output: 23

시행착오

이 문제는 세션에서 이미 완성된 코드로 확인해서, 실제로 어떤 시행착오를 거쳤는지는 대화 기록에 남아있지 않다 (지어내지 않기 위해 솔직하게 밝힌다). 대신 최종 코드가 어떤 논리로 짜였는지를 단계별로 풀어본다.

1. 무엇을 이진 탐색할 것인가: 배열의 원소나 인덱스가 아니라, 답이 될 수 있는 “속도 k” 자체를 탐색 대상으로 잡는다. k의 최솟값은 1, 최댓값은 가장 큰 더미의 크기(그 이상 빨리 먹을 필요가 없으므로).
2. 각 후보 k가 조건을 만족하는지 어떻게 판정할 것인가: k로 모든 더미를 다 먹는 데 걸리는 시간을 더해서 h 이하인지 확인한다. 한 더미를 먹는 시간은 ceil(piles[i] / k), 즉 (piles[i] + k - 1) / k로 올림 나눗셈한다.
3. 범위를 어느 쪽으로 좁힐 것인가: 걸리는 시간이 h보다 크면 k가 너무 느린 것이므로 k를 키워야 한다(left = mid + 1). h 이하면 k를 줄여도 되는지 계속 확인해야 하므로 right = mid - 1로 좁히면서 더 작은 k를 계속 찾는다.

최종 코드

public static int minEatingSpeed(int[] piles, int h) {
    int left = 1;
    int right = piles[0];
    for (int p : piles) {
        if (p > right)
            right = p;
    }

    while (left <= right) {
        int mid = left + (right - left) / 2;
        long time = 0;
        int idx = 0;
        while (!(idx == piles.length) && (time <= h)) {
            time += (piles[idx] + mid - 1) / mid;
            idx++;
        }
        if (time > h) {
            left = mid + 1;
        } else if (time <= h) {
            right = mid - 1;
        }
    }

    return left;
}

변수 추적표 (piles = [3,6,7,11], h = 8)

반복	left	right	mid	걸리는 시간 합	비교	갱신
1	1	11	1+(11-1)/2=6	1+1+2+2=6	6 <= 8	right = 5
2	1	5	1+(5-1)/2=3	1+2+3+4=10	10 > 8	left = 4
3	4	5	4+(5-4)/2=4	1+2+2+3=8	8 <= 8	right = 3
—	4	3	left(4) <= right(3)? 거짓 → 종료

루프 종료 시 left = 4 → 정답 4

오늘 배운 내용

이 문제에서 가장 중요한 내용은 파라메트릭 서치의 정체다. 지금까지 풀었던 이진 탐색은 “정렬된 배열 안에서 특정 값(또는 조건을 만족하는 위치)을 찾는” 것이었는데, 이 문제는 다르다. 탐색 대상 자체가 배열이 아니라 “답이 될 수 있는 값의 범위”이고, 각 후보값이 조건을 만족하는지는 매번 배열 전체를 순회해서 계산해야 한다. 그래서 시간복잡도도 O(log(range) * n)이 된다 — 이진 탐색 한 번마다 배열 전체를 훑는 비용이 추가로 붙는다는 뜻이다.

오답노트

이번엔 직접 겪은 실수를 관찰할 수 있는 기록이 없어서, 이 유형에서 일반적으로 놓치기 쉬운 지점을 정리해둔다.

• 탐색 범위를 배열 인덱스로 착각하기 쉽다: 파라메트릭 서치의 left/right는 배열의 인덱스가 아니라 “답의 최솟값/최댓값”이다. 이 문제에서는 1과 max(piles)가 범위다.
• 올림 나눗셈을 빠뜨리기 쉽다: “속도 k로 다 먹으려면 몇 시간 걸리나”는 piles[i] / k가 아니라 ceil(piles[i] / k) = (piles[i] + k - 1) / k다. 정수 나눗셈을 그대로 쓰면 답이 항상 더 작게 나온다.
• 총합의 오버플로우: 더미가 최대 10^4개, 각 더미가 최대 10^9개라 시간 합이 int 범위를 넘을 수 있다. 이 코드에서도 time을 long으로 선언한 이유가 여기 있다.

꿀팁

• 문제에서 “최소 k를 찾아라 / 이 조건을 만족하는 가장 작은(또는 큰) 값을 찾아라”라는 문장이 나오면, 배열을 직접 탐색하는 대신 답의 범위를 이진 탐색하는 파라메트릭 서치를 의심해본다.
• 판정 함수(조건을 만족하는지 확인하는 부분)를 먼저 별도로 생각해두면, 그 다음에 어느 쪽으로 범위를 좁힐지는 자연스럽게 따라온다.