LeetCode 1482 Minimum Number of Days to Make Bouquets

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

---

문제해석 및 요약 : 날짜 배열이 주어질 때 해당 날짜가 지난 후에 꽃이 생긴다. m개의 부케를 만드는데 인접한 꽃을 가지고 k개만큼 묶어서 부케를 만들어라. 그 때 최소날짜는??

예시

bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3

7일 일 때

0,0,0,0,x,O,O  ----->  이렇게 꽃이 생기는데 인접한 꽃을 가지고 3개씩 묶음을 가지고 만들어야 해서 12일 칸에는 꽃이 없어 부캐를 최대 1개 밖에 못 만듬

 

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

 

문제해결 KEY POINT

- bloomDay의 min 값과 max 값 사이에 정답이 있다

- 이진탐색을 이용해서 최솟값을 구해보자

 

정답코드

import java.util.*;

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {

        int N = bloomDay.length;

        if(N < m*k) return -1;


        int min = 1000000010;
        int max = 0;

        for(int i=0; i<bloomDay.length; i++){
            min = Math.min(min, bloomDay[i]);
            max = Math.max(max, bloomDay[i]);
        }

        int s = min;
        int e = max;

        int ans = 0;

        while(s <= e){

            int mid = (s+e)/2;

            int cnt = 0;
            int tmp = 0;

            for(int i=0; i<N; i++){
                if(mid >= bloomDay[i]){
                    tmp++;
                    if(tmp == k) {
                        cnt++;
                        tmp = 0;
                    }
                }
                else
                    tmp = 0;
            }

            if(cnt >= m){
                 e = mid - 1;
                 ans = mid;
            }
               
            else
                s = mid + 1;


        }

        if(ans == 0) 
            return -1;
        else
            return ans;

    }
}