Leetcode - 875. Koko Eating Bananas

문제

코코라는 동물(원숭이?)이 바나나더미를 먹는다. 사육사가 오기 전까지 제한시간이 주어지고 모든 더미를 먹어야한다. 시간당 최소한으로 먹을수 있는 갯수는?
(단, 만약 시간당23개를 먹을 수 있다면, 30은 두시간이 걸리고, 11은 1시간이 걸린다.)

Input: piles = [30,11,23,4,20], h = 6
Output: 23

https://leetcode.com/problems/koko-eating-bananas/

해결 O(nlogn)

이 문제도 템플릿을 이용한 Binary search문제다. Up & Down으로 정답을 찾고 그것을 찾을때 배열값을 가지고 계산(O(n))한다.

class Solution {
    bool condition(vector<int> piles, int speed, int limit_h) {
        // check the speed is enough to finish all of banana piles
        int tot_time = 0;
        for (int i = 0; i < piles.size(); i++)
            tot_time += (piles[i] / speed) + (piles[i] % speed != 0);
        if (tot_time <= limit_h)
            return true;
        return false;
    }
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1;
        int right = *std::max_element(piles.begin(), piles.end());
        int mid = 0;
        
        while (left < right) {
            mid = left + (right - left) / 2;
            if (condition(piles, mid, h))   // enough speed. much less speed could be enough as well.
                right = mid;
            else                            // too slow                           
                left = mid + 1;
        }
        return left;
    }
};

맨처음에 condition계산을 아래와같이 했는데 TLE가 나왔다. 근데 그냥 단순계산으로 해결할수 있는거였다.

    bool condition(vector<int> piles, int speed, int limit_h) {
        int idx = 0;
        
        while (idx < piles.size()) {
            if (speed >= piles[idx]) {
                piles[idx] = 0;
                idx++;
            } else {
                piles[idx] = piles[idx] - speed;
            }
            hour--;
            if (hour < 0)
                break;
        }
        if (hour >= 0)
            return true;
        return false;
    }