Minimum Number of Days to Make m Bouquets

KoKo eating banana 문제랑 굉장히 유사하게 느껴졌다. 이런 문제에서는 최소의 시간이 걸리는 구간을 찾기 위해서 binary search 를 통해서 얻는게 가장 좋다.

특정 시간을 얻게 되면 그 시간대로 search 를 해주고 얼마나 많은 Bouquets 를 구할 수 있는지만 잘 확인해준다면 어렵지 않게 구할 수 있다.

/*
Time Complexity : O(n log n) 
Space Complexity : O(1) 
*/
class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        long long n = bloomDay.size(); 
        if((long long)m * (long long)k > n) return -1; 

        int right = *max_element(bloomDay.begin(), bloomDay.end()); 
        int left = 0; 
        while(left <= right){
            int mid = (right + left) / 2; 

            int tmpM = 0, tmpK = k;  
            for(int i = 0; i < bloomDay.size(); i++){
                int flower = bloomDay[i]; 

                if(flower <= mid){
                    tmpK--; 
                    if(tmpK == 0){
                        tmpM++; 
                        tmpK = k; 
                    }
                } else{
                    tmpK = k; 
                }
            }

            if(tmpM >= m){
                right = mid-1; 
            } else{
                left = mid + 1; 
            }
        }

       
        return left; 
    }
};