[LeetCode] 875. Koko Eating Bananas, Medium

1. 문제

• 정수 배열 piles가 주어질 때, 1시간에 임의의 값 k만큼 각 요소를 삭제할 수 있다고 하자.
• 정수 h시간 전에 모든 요소를 삭제할 수 있는 최소 k를 구하라.

2. 해결

function getTotalHours(piles: number[], k: number) : number {
    let total = 0;

    for(let pile of piles) {
        total += Math.ceil(pile / k);
    }

    return total;
}
function minEatingSpeed(piles: number[], h: number): number {
    let left = 1, right = Math.max(...piles);

    while(left < right) {
        const mid = Math.floor((left + right) / 2);
        const time = getTotalHours(piles, mid);

        if(time <= h) right = mid;
        else left = mid + 1;
    }

    return left;
};

• 이진 탐색 문제에서 처음 보는 유형.
• 값의 범위 내에서 조건을 만족하는 최소/최댓값을 찾을 때 이진 탐색을 사용한다.
• 여기서 값의 범위는 k로 k는 한 시간에 먹을 수 있는 바나나의 양이다.
• 즉 범위는 1개부터 최대 바나나 개수까지 가능.
• 이 범위에서 중간 값을 구해 이걸 기준으로 전체 바나나를 먹는 총 시간을 구한다.
• 총 시간이 h보다 작은 경우 더 먹어도 될 수 있기 때문에, 왼쪽으로 좁혀 최솟값을 찾는다.
• 그 외에는 시간이 초과되기 때문에 더 많이 먹어야 해서 오른쪽으로 좁혀 최솟값을 찾는다.