문제 - 1482

문제 설명

1. m 개의 부케를 만들어야 된다.
2. 부케를 만들기 위해서는 k만큼 이웃된 꽃들이 필요함.
3. 꽃이 피는 날은 bloomDay에 저장되어 있다.
   예시를 보면 이해하기 편하다.
   bloomDay가 [1,10,3,10,2]이며 m = 3, k =1 일 때
   1일차 : [O, X, X, X, X] 부케하나 완성 bouquet = 1;
   2일차 : [O, X, X, X, O] 부케하나 완성 bouquet = 2;
   3일차 : [O, X, O, X, O] 부케하나 완성 bouquet = 3;
   최종으로 3개를 만들기 위해서는 3일이 필요하다.

문제 접근

이분탐색으로 start = 0, end = bloomDay에서 제일 큰 날짜로 설정
날짜는 start + end / 2 로 기준으로 꽃이 몇개 피었는지 확인한다.
기준 날짜에 최대로 만들 수 있는 부케로 start와 end를 변경
bouquest의 갯수가 >= m : end = mid -1 갯수가 더 큰 경우이므로 조금 더 날짜를 낮게 만들 기 위해서
반대로는 start = mid +1 기준 날짜를 좀 더 크게만들기 위해서

import java.util.*;

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int start = 0, end = 0, ans = -1;
        int n = bloomDay.length;
        for(int i=0;i<n;i++)
        {
            end = Math.max(bloomDay[i],end);
        }

        while(start <= end)
        {
            int mid = (start + end) /2;
            int bouquests = getNumOfBouquests(mid,bloomDay,k);
            
            if(bouquests >= m)
            {
                end = mid -1;
                ans = mid;
            }else
            {
                start = mid + 1;
            }
        }

        return ans;
    }

    int getNumOfBouquests(int day, int[] bloomDay, int limit)
    {
        int bouquests = 0;
        int count = 0;
        for(int i=0; i < bloomDay.length; i++)
        {
            //bloomed
            if(bloomDay[i] <= day)
            {
                count++;
            }else{//not bloomed
                count = 0;
            }

            if(count == limit)
            {
                count = 0;
                bouquests++;
            }
        }

        return bouquests;
    }
}