[LeetCode] 1482. Minimum Number of Days to Make m Bouquets

https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/description/

leetcode - Minimum Number of Days to Make m Bouquets

문제 유형 : 이진탐색, 그리디, 슬라이딩 윈도우, 구현

문제 난이도 : Medium

 

문제

You are given an integer array bloomDay, an integer m and an integer k.

You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

정수 bloomDay, 정수 m, k를 받습니다.

당신은 m개의 부케를 만들려고 합니다. k개의 인접한 꽃들로 부케를 만들 수 있습니다.

정원에는 n개의 꽃이있고 bloomday[i]에 i번째 자리의 꽃이 하나 핍니다.

m개의 부케를 만들기 위한 최소 걸리는 날짜를 구하시오.

불가능하면 -1을 반환하시오.

 

풀이

우선, m * k보다 n이 작은면 -1을 반환한다.

 

이진 탐색으로 접근할 수 있다. left를 1, right를 bloomDay의 최대값.

그리고 날짜를 이진탐색으로 조율하면 되는데, 

선형적으로 bloomDay를 순회하면서 슬라이딩 윈도우를 이용해서 꽃 묶음들을 계산한다.

만약 m개의 부케를 만들 수 있다면, right을 mid로 한다. 더 줄여볼 수 있기 때문이다.

만약 불가능하다면, left를 mid+1로 한다. 더 많은 날들을 기다려야 하기 때문이다.

 

최종 리턴으로 left를 해주면 되겠다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    int n;
public:
    bool check(vector<int>& bloomDay, int m, int k, int day) {
        int i = 0;
        int bouquets = 0;
        while (i < n) {
            int cnt = 0;
            while (i < n && cnt < k && bloomDay[i] <= day) {
                i++;
                cnt++;
            }
            if (cnt == k) bouquets++;
            if (bouquets == m) return true;
            while (i < n && bloomDay[i] > day) {
                i++;
            }
        }
        return false;
    }

    int minDays(vector<int>& bloomDay, int m, int k) {
        n = bloomDay.size();
        if ((long long)m * k > n) return -1;

        int left = 1, right = *max_element(bloomDay.begin(), bloomDay.end());
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(bloomDay, m, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};