LeetCode

LeetCode 875 Koko Eating Bananas 풀이: 가능 여부 판정 이분 탐색

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

바나나를 얼마나 빨리 먹어야 하는지 계산할 때 각 더미를 먹는 데 걸리는 시간을 더해야 한다. 여기에 5개를 시간당 2개 먹으면 2시간이 아니라 3시간이 걸리는 올림 계산과, 가능한 속도 범위를 절반씩 줄이는 이분 탐색이 함께 필요하다. 기본 반복문으로 판정 함수를 만들고 경계를 갱신하는 문제이므로 Level 2로 판단했다.

1. 문제 요약

코코는 여러 바나나 더미를 가지고 있고, 매시간 한 더미에서 정해진 개수만큼 먹는다. 한 시간에 선택한 더미를 모두 먹지 못하면 그 시간에는 더 먹지 않고 다음 시간으로 넘어간다. 주어진 h시간 안에 모든 바나나를 먹을 수 있는 최소 시간당 섭취량 k를 반환한다.

중요한 조건은 다음과 같다.

  • 바나나 더미 배열 piles의 길이는 1 이상 10^4 이하이다.
  • 각 더미의 바나나 수는 1 이상 10^9 이하이다.
  • 제한 시간 h는 1 이상 10^9 이하이다.
  • 한 시간에 먹는 양은 하나의 더미에서만 차감된다.
  • 각 더미에 필요한 시간은 ceil(pile / k)이다.

속도 k가 정해지면 각 더미를 먹는 데 필요한 시간을 계산해 총합을 구할 수 있다. 속도가 빠를수록 필요한 시간은 줄어들므로, 가능한 속도와 불가능한 속성이 경계에서 나뉘는 단조성이 생긴다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

판정 함수와 탐색 구간

속도 speed가 주어졌을 때 필요한 총 시간은 다음과 같다.

required_hours = sum(ceil(pile / speed) for pile in piles)

Python에서는 올림 나눗셈을 (pile + speed - 1) // speed로 계산한다. required_hours 가 h 이하이면 해당 속도는 가능한 속도이고, h보다 크면 불가능한 속도다.

속도는 최소 1부터 최대 더미 크기 max(piles) 사이에 있다. 최대 더미 크기만큼 먹으면 가장 큰 더미를 한 시간에 끝낼 수 있고, 모든 더미를 순서대로 처리하는 최댓값이므로 항상 가능한 상한이다.

속도에 따라 가능 여부가 단조롭게 바뀌는 이유

속도가 k일 때 가능하다면, k보다 더 빠른 속도도 반드시 가능하다. 반대로 k가 불가능하다면 더 느린 속도 역시 불가능하다. 그래서 속도 후보는 다음과 같은 형태를 가진다.

불가능한 속도 | 가능한 속도

이 경계에서 가장 작은 가능한 속도를 찾으면 된다. 매번 중간 속도 mid를 판정하고, 가능하면 right = mid로 상한을 줄이며, 불가능하면 left = mid + 1로 하한을 올린다.

공식 예제 piles = [3, 6, 7, 11], h = 8을 판정해 보면 속도 3은 1 + 2 + 3 + 4 = 10시간이 필요해 불가능하고, 속도 4는 1 + 2 + 2 + 3 = 8시간이므로 가능하다.

속도 k 더미별 필요 시간 총 시간 판정
3 1, 2, 3, 4 10 불가능
4 1, 2, 2, 3 8 가능

가능한 속도에서는 mid 자체가 정답일 수 있으므로 right = mid로 남기고, 불가능한 속도는 정답이 될 수 없어 left = mid + 1로 제외한다.

경계 불변식과 판정 기준

탐색 구간 [left, right]는 정답이 반드시 포함된 닫힌 구간이다. left == right가 되면 가능한 속도 중 가장 작은 하나만 남은 것이므로 이를 반환한다.

required_hours가 h와 같을 때도 제한 시간 안에 먹을 수 있으므로 가능한 속도로 처리해야 한다. 그래서 조건은 required_hours <= h다. 반대로 반복문 안에서 hours > h가 되는 즉시 합계를 중단해도 되지만, 이 글의 구현은 판정식을 단순하게 유지하기 위해 전체 합을 계산한다.

오답 접근과 반례

속도를 1부터 증가시키며 처음 가능한 값을 찾으면 정답은 얻을 수 있지만, 최악의 경우 속도가 10^9까지 증가해 매우 많은 판정이 필요하다.

piles = [1000000000]
h = 1

이 입력의 정답은 1000000000이다. 선형으로 속도를 시도하면 최대 범위만큼 반복하지만, 이분 탐색은 속도 범위를 절반씩 줄인다.

필요한 시간을 pile // speed로 계산하면 올림이 사라져 실제보다 적은 시간을 계산한다. 예를 들어 pile = 5, speed = 2이면 필요한 시간은 3이지만 5 // 2는 2다. 반드시 올림 나눗셈을 사용해야 한다.

시간·공간 복잡도

속도 탐색 범위는 1부터 m = max(piles)까지이며, 이분 탐색 횟수는 O(log m)이다. 각 판정마다 n개의 더미를 확인하므로 시간 복잡도는 O(n log m)이다. 누적 시간과 경계만 저장하므로 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

left와 right는 가능한 정답의 범위다. speed로 각 더미를 먹는 데 필요한 시간을 합산한 뒤, 제한 시간 이내인지에 따라 가능한 경계를 유지한다.

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left = 1
        right = max(piles)

        while left < right:
            speed = left + (right - left) // 2
            hours = sum((pile + speed - 1) // speed for pile in piles)

            if hours <= h:
                right = speed
            else:
                left = speed + 1

        return left

right = speed로 갱신하는 이유는 현재 속도가 가능하므로 정답일 가능성을 버리면 안 되기 때문이다. 반면 불가능한 speed는 정답이 될 수 없으므로 left = speed + 1로 제외한다. left < right를 반복 조건으로 사용하면 마지막 가능한 속도 하나가 남았을 때 바로 반환할 수 있다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 속도 경계와 올림 나눗셈을 재현할 수 있다.

solver = Solution()
assert solver.minEatingSpeed([3, 6, 7, 11], 8) == 4
assert solver.minEatingSpeed([30, 11, 23, 4, 20], 5) == 30
assert solver.minEatingSpeed([5], 3) == 2

4. 공식 예제와 추가 검증

작성한 minEatingSpeed 함수를 Python으로 실행해 공식 예제와 최소 입력, 최대 속도, 올림 나눗셈 조건을 확인했다.

공식 예제

입력 기대 결과 확인 결과
piles = [3,6,7,11], h = 8 4 통과
piles = [30,11,23,4,20], h = 5 30 통과
piles = [30,11,23,4,20], h = 6 23 통과

추가 검증 1: 더미 하나

입력: piles = [1], h = 1
기대 출력: 1
확인 결과: 통과
검증 목적: 최소 입력에서 한 시간에 하나를 먹는 속도를 확인

추가 검증 2: 모든 더미를 정확히 한 시간씩 처리

입력: piles = [1, 1], h = 2
기대 출력: 1
확인 결과: 통과
검증 목적: 가장 느린 속도에서도 더미마다 한 시간이 주어지는 경우 확인

추가 검증 3: 최대 크기 더미

입력: piles = [1000000000], h = 1
기대 출력: 1000000000
확인 결과: 통과
검증 목적: 속도 탐색의 상한이 정답이 되는 경계 확인

추가 검증 4: 올림 나눗셈이 필요한 경우

입력: piles = [5], h = 3
기대 출력: 2
확인 결과: 통과
검증 목적: 5를 속도 2로 먹는 데 3시간이 필요하다는 올림 계산 확인

5. 다른 풀이 방식 검색 및 비교

속도를 작은 값부터 선형으로 시도하는 방법은 구현이 직관적이지만, 최대 더미 크기가 10^9까지 가능해질 수 있다. 이분 탐색은 각 속도에서 필요한 시간을 계산하는 판정 함수는 그대로 사용하면서 후보 속도의 범위를 O(log m)번 줄인다.

판정 과정에서 누적 시간이 이미 h를 초과하면 즉시 반복을 중단하는 최적화도 가능하다. 이 글에서는 알고리즘의 핵심인 단조 판정과 경계 갱신을 명확하게 보이도록 전체 합을 계산하는 방식을 사용했다.

마무리

Koko Eating Bananas는 속도 자체를 바로 계산하는 문제가 아니라, 특정 속도가 제한 시간 안에 가능한지 판정하고 최소 가능한 값을 찾는 문제다. ceil(pile / speed)를 이용해 시간을 계산하고 [1, max(piles)] 범위에서 이분 탐색하면 O(n log m) 시간과 O(1) 공간으로 해결할 수 있다. 가능한 경우에도 현재 중간 속도를 후보로 남기는 right = speed가 핵심이다.

#이분탐색#LeetCode#난이도 2