Koko Eating Bananas

Q: 코코가 바나나를 먹는 데 걸리는 시간 복잡도는 얼마인가요?

이진 탐색은 O(n log m) 시간에 실행됩니다. 여기서 n 은 더미의 개수이고 m 은 가장 큰 더미입니다. 약 log2(m) 번 확인하며, m = 10^9 일 때는 30번 확인합니다. 각 확인에서는 모든 더미를 한 번씩 읽습니다. 추가 공간은 O(1) 입니다.

Q: 속도의 하한과 상한은 얼마인가요?

상한은 가장 큰 더미입니다. 이 경우 모든 더미를 한 시간씩 먹으면 되므로 항상 시간 안에 끝낼 수 있습니다. 하한은 1이며, 코코는 한 시간에 최대 k 개의 바나나를 먹으므로 전체 바나나 수를 h 로 나누고 올림한 값까지 높일 수 있습니다.

Q: 정수를 사용해 나눈 뒤 올림하려면 어떻게 하나요?

정수 나눗셈을 사용해 (p + k-1) / k 를 사용하세요. k-1 을 더하면 나머지가 다음 k 의 배수를 넘어서고, 정확한 배수는 그대로 유지됩니다. 속도가 4일 때 10은 13 / 4 = 3 이 되고, 8은 11 / 4 = 2 가 됩니다. 부동 소수점 연산은 필요하지 않습니다.

보통이진 탐색

+10

Koko에게는 바나나 더미가 n개 있고, i번째 더미에는 바나나가 piles[i]개 있으며, 시간은 h시간 주어집니다. Koko는 시간당 먹을 바나나 개수인 정수 k를 하나 정하고 계속 그 속도로 먹습니다. 매시간 한 더미에서 바나나를 k개 먹습니다. 그 더미에 남은 바나나가 k개보다 적으면 모두 먹고, 시간이 끝날 때까지 쉽니다. h시간 안에 모든 더미를 먹을 수 있게 하는 가장 작은 k를 반환하세요.

함수

minEatingSpeed(piles: integer-array, h: integer) → integer

pilesinteger-array: 각 더미에 있는 바나나의 개수
hinteger: Koko가 가진 시간
반환값integer: h시간 이내에 모든 더미를 먹을 수 있는, 시간당 바나나 수로 나타낸 가장 낮은 정수 먹는 속도

제약 조건

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹이므로 항상 답이 존재합니다.

예제

입력: piles = [4, 10, 7, 3]h = 6
출력: 5
설명: 속도 5에서는 더미 4, 10, 7, 3을 처리하는 데 각각 1, 2, 2, 1시간이 걸립니다. 총 6시간이므로 조건에 맞습니다. 속도 4에서는 각각 1, 3, 2, 1시간이 걸리며, 총 7시간입니다.

후속 질문

쌍둥이 문제: 코코는 하루에 최대 k개의 바나나를 먹으며, d일 안에 순서대로 더미 전체를 먹습니다. 가장 작은 k는 얼마이며, 탐색에서 무엇이 달라지나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

정답은 배열에서의 위치가 아니라 속도이며, 이 점 때문에 이진 탐색을 사용할 수 있습니다. 속도 하나를 확인할 때는 더미를 한 번씩 모두 살펴보며, 속도 k로 시간 안에 끝낼 수 있다면 그보다 빠른 모든 속도로도 끝낼 수 있습니다. 따라서 1부터 가장 큰 더미까지의 속도를 이진 탐색하면 최대 10억 번 대신 약 30번만 확인하면 됩니다.

1부터 시작해 모든 속도를 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

Koko는 한 시간 안에는 다른 더미로 이동하지 않으므로, 바나나가 p개 있는 더미를 먹는 데는 올림하여 p / k시간이 걸립니다. 속도가 4일 때 10개를 먹는 데는 3시간이 걸립니다. 속도 1, 2, 3 등을 차례로 시도하고, 총 시간이 h 이내에 드는 첫 번째 속도를 반환하세요. 그보다 느린 속도는 모두 실패했으므로 이 속도가 가장 작습니다. 또한 가장 큰 더미의 속도에 도달하면 각 더미를 먹는 데 한 시간씩 걸리므로 반복문은 그때 멈춥니다.

m을 가장 큰 더미라고 하면, n개의 더미를 최대 m번 확인합니다. 더미가 5000개이고 각 더미가 10^9에 가까우며 h = 5000일 때 약 5 × 10^12번의 연산이 필요합니다.

알고리즘

speed = 1로 설정합니다.
이 속도로 걸리는 시간을 계산합니다. 각 더미마다 (pile + speed-1) / speed를 더하고, 합계는 64비트 정수로 저장합니다.
합계가 h 이하이면 speed를 반환합니다.
그렇지 않으면 speed를 1 증가시키고 다시 계산합니다.

def minEatingSpeed(piles, h):
    speed = 1
    while True:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # a started pile costs a whole hour
        if hours <= h:
            return speed
        speed += 1

속도에 대한 이진 탐색

핵심 아이디어

속도가 증가하면 각 더미를 처리하는 데 걸리는 시간은 같거나 줄어들므로, “이 속도로 시간 내에 끝낼 수 있는가?”에 대한 답은 첫 번째 ‘예’가 나올 때까지 아니요, 아니요, 아니요, 그다음부터 예가 됩니다. 이진 탐색은 첫 번째 ‘예’를 찾습니다.

항상 답을 포함하는 lo부터 hi까지의 범위를 유지합니다. 처음에는 1과 가장 큰 더미로 시작합니다. 가장 큰 더미의 속도로는 더미마다 한 시간이 걸리므로 시간 내에 끝낼 수 있습니다. 중간 속도 mid로 끝낼 수 있다면 답은 mid 또는 그보다 느린 속도이므로 hi = mid로 설정합니다. 끝낼 수 없다면 그보다 느린 모든 속도도 실패하므로 lo = mid + 1로 설정합니다. lo가 hi와 같아지면 그것이 답입니다.

첫 번째 예시에서 범위는 1부터 10까지로 시작합니다. 속도 5로 끝낼 수 있으므로 범위는 1부터 5까지가 됩니다. 속도 3으로는 10시간이 걸리므로 범위는 4부터 5까지가 됩니다. 속도 4로는 7시간이 걸리므로 범위는 5부터 5까지가 됩니다.

알고리즘

lo = 1로 설정하고 hi를 가장 큰 더미로 설정합니다.
lo < hi인 동안 mid = lo + (hi - lo) / 2를 구합니다.
속도 mid에서 걸리는 시간을 계산합니다. 각 더미마다 (pile + mid-1) / mid를 더하고, 합계는 64비트 정수로 저장합니다.
합계가 h 이하이면 hi = mid로 설정하고, 그렇지 않으면 lo = mid + 1로 설정합니다.
lo를 반환합니다.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)  # the largest pile always works: one hour per pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = 0
        for pile in piles:
            hours += (pile + mid - 1) // mid
        if hours <= h:
            hi = mid  # mid works, so the answer is mid or slower
        else:
            lo = mid + 1  # mid is too slow, so the answer is faster
    return lo

함정과 경계 사례

시간 합계의 오버플로. 속도가 1일 때 10^9바나나 더미 5000개는 5 × 10^12시간이 걸려 32비트 한계를 넘으며, 합계가 오버플로되면 느린 속도도 통과할 수 있습니다. 64비트로 계산하거나 합계가 h를 초과하는 즉시 멈추세요.
내림. 10 / 4는 2가 되지만, 해당 더미를 처리하는 데는 3시간이 걸립니다.
범위를 0에서 시작하기. 그러면 mid가 0이 될 수 있고, 계산할 때 0으로 나누게 됩니다.
mid가 조건을 만족할 때 hi = mid - 1로 설정하기. 그러면 정답을 제외할 수 있습니다.
가장 큰 더미보다 작은 값으로 hi를 시작하기. h가 더미의 개수와 같으면, 그보다 낮은 모든 속도는 조건을 만족하지 못하며 탐색 결과로 그중 하나가 반환됩니다.

자주 묻는 질문3

코코가 바나나를 먹는 데 걸리는 시간 복잡도는 얼마인가요?

이진 탐색은 O(n log m) 시간에 실행됩니다. 여기서 n은 더미의 개수이고 m은 가장 큰 더미입니다. 약 log2(m)번 확인하며, m = 10^9일 때는 30번 확인합니다. 각 확인에서는 모든 더미를 한 번씩 읽습니다. 추가 공간은 O(1)입니다.

속도의 하한과 상한은 얼마인가요?

상한은 가장 큰 더미입니다. 이 경우 모든 더미를 한 시간씩 먹으면 되므로 항상 시간 안에 끝낼 수 있습니다. 하한은 1이며, 코코는 한 시간에 최대 k개의 바나나를 먹으므로 전체 바나나 수를 h로 나누고 올림한 값까지 높일 수 있습니다.

정수를 사용해 나눈 뒤 올림하려면 어떻게 하나요?

정수 나눗셈을 사용해 (p + k-1) / k를 사용하세요. k-1을 더하면 나머지가 다음 k의 배수를 넘어서고, 정확한 배수는 그대로 유지됩니다. 속도가 4일 때 10은 13 / 4 = 3이 되고, 8은 11 / 4 = 2가 됩니다. 부동 소수점 연산은 필요하지 않습니다.

def minEatingSpeed(piles, h):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

piles = [4, 10, 7, 3]
h = 6

예상 출력