[2024] day 172 Leetcode 1482. Minimum Number of Days to Make m Bouquets

gunny·2024년 6월 19일

leetcode 1482. Minimum Number of Days to Make m Bouquets leetcode 1482. Minimum Number of Days to Make m Bouquets python

코딩테스트

목록 보기

486/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 19일 (수)
Leetcode daily problem

1482. Minimum Number of Days to Make m Bouquets

https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/?envType=daily-question&envId=2024-06-19

Problem

정수 배열 BloomDay과 정수 m 및 정수 k가 제공된다.
여기서 주어진 정수 m개 만큼의 꽃다발을 만들고자 하는데, 꽃다발을 만들기 위해서는 정원에 있는 k개의 인접한 꽃을 사용해야 한다.

정원은 n개의 꽃으로 구성되어 있고, i번째 꽃은 BloomDay[i]에 피고 정확히 하나의 꽃다발에 사용될 수 있다.

정원에서 m개의 꽃다발을 만들기 위해 기다려야 하는 최소 일수를 반환한다다. m개의 꽃다발을 만드는 것이 불가능하면 -1을 반환한다.

Solution

binary search

주어진 배열에서 연속된 k개의 꽃을 포함해 m개의 부케를 만드는 것이 문제이다. 단순한 방법은 1일부터 시작해서 m개의 부캐를 만들 수 있는 첫 번째 날을 찾는 것이다.
특정 날에 몇 개의 부케를 만들 수 있는지 확인하는 방법은 각 부캐에 연속된 k개의 꽃이 필요하다는 것을 알고 있으므로, 연속된 피어 있는 꽃을 찾아서 그 수가 k와 같다면 하나의 부케를 만들 수 있다고 생각하면 된다.

연속된 피어 있는 꽃의 수가 k보다 작다면 해당하지 않으므로 만들 수 있는 부케가 m 이상이면 그 날이 답이 되게 된다.

이렇게 찾는 과정에서 처음부터 끝까지 날짜를 찾는 것은 비효율적이므로, 이진 탐색을 사용해서 1일부터 주어진 bloomDay의 배열에서의 최대값을 가지는 요일 사이의 이진 탐색을 사용해서 빠르게 해당 날을 찾아낸다.

Code

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        
        def getBouquets(bloomDay, mid, k):
            bouquet = 0
            cnt = 0
            
            for day in bloomDay:
                if day <= mid:
                    cnt +=1
                else:
                    cnt = 0
                
                if cnt == k:
                    bouquet +=1
                    cnt =0
                    
            return bouquet
        
        
        ans=-1
        l,r = 0, max(bloomDay)
        while l<=r:
            mid = (l+r)//2
            if getBouquets(bloomDay, mid, k) >= m:
                ans = mid
                r = mid-1
            else:
                l = mid+1
                
        return ans