Leetcode - 1482. Minimum Number of Days to Make m Bouquets

문제

몇일 뒤에 꽃이 피는지가 적힌 bloomDay[] 배열이 주어진다. 꽃이 피면 꽃다발을 만들수 있다. 하나의 꽃다발은 k개이어야하고, 반드시 인접한 꽃만 선택할 수 있다. 총 m개의 꽃다발을 만든다고 할때, 최소 몇일 뒤에 작업을 완수할수 있는가?

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

아이디어

• 이전 문제와 마찬가지로 템플릿을 이용한 이진탐색 문제, Up & Down 형식의 이진탐색 문제다.

해결

class Solution {
    bool condition(vector<int> bloomDay, int remain_days, int m, int k) {
        // check k's continous subarray are exist m times
        int cont_cnt = 0;
        
        for (int i = 0; i < bloomDay.size(); i++) {
            cont_cnt++;
            if (bloomDay[i] > remain_days) {
                if (cont_cnt-1 >= k)
                    m--;
                cont_cnt = 0;
            } else if (cont_cnt >= k) {
                m--;
                cont_cnt = 0;
            }
            if (m <= 0)
                return true;
        }

        if (cont_cnt >= k)
            m--;
        if (m <= 0)
            return true;
        return false;
        
    }
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if (m * k > bloomDay.size())
            return -1;
        int left = *std::min_element(bloomDay.begin(), bloomDay.end());
        int right = *std::max_element(bloomDay.begin(), bloomDay.end());
        int mid = 0;
        
        while (left < right) {
            mid = left + (right - left) / 2; // the remain days what we have to find
            
            if (condition(bloomDay, mid, m, k)) // check mid days is possible to make bouquet
                right = mid;
            else                                // it's not possible
                left = mid + 1;
        }
        return left;
    }
};