파이썬(Python)으로 m개의 꽃다발을 만드는 데 필요한 최소 일수 구하기

정수로 이루어진 배열 nums와 두 개의 값 m, k가 있다고 가정해 봅시다. 우리는 정원에서 꽃다발 m개를 만들어야 하고, 꽃다발 하나를 만들려면 인접한(연속된) 꽃 k송이가 필요합니다. 정원에는 서로 다른 꽃 n송이가 있으며, i번째 꽃은 bloomDay[i]번째 날에 핍니다. 각 꽃은 단 하나의 꽃다발에만 사용할 수 있습니다. 이때 꽃다발 m개를 완성하기 위해 기다려야 하는 최소 일수를 구하고, 만드는 것이 불가능하다면 -1을 반환해야 합니다.

예시

bloomDay = [5,5,5,5,10,5,5], m = 2, k = 3이라면 결과값은 10입니다. 꽃다발 2개(m = 2)가 필요하고 각각 꽃 3송이(k = 3)를 포함해야 하기 때문입니다.

5일째 되는 날: [x, x, x, x, _, x, x] — 먼저 핀 앞쪽 세 송이의 꽃으로 꽃다발 하나는 만들 수 있지만, 뒤에는 두 송이밖에 남지 않아 두 번째 꽃다발은 만들 수 없습니다.
10일째 되는 날: [x, x, x, x, x, x, x] — 모든 꽃이 피었으므로 여러 가지 방법으로 꽃다발 두 개를 만들 수 있습니다.

풀이 접근 방법: 이진 탐색(Binary Search)

이 문제의 핵심은 이진 탐색입니다. 특정 날짜 x가 주어졌을 때 그날까지 꽃다발 m개를 만들 수 있는지 판단하는 함수 possible()을 정의한 뒤, 답이 될 수 있는 날짜 범위를 절반씩 좁혀 가며 최솟값을 찾습니다. 날짜가 늦어질수록 조건을 만족하기 쉬워지는 성질(단조성)이 있기 때문에 이진 탐색을 적용할 수 있습니다.

1. 가능 여부 검사 함수 possible(x)

count := 0, bouquets := 0으로 초기화합니다.
bloomDay의 각 요소 d에 대해 다음을 반복합니다.
- d ≤ x이면 count를 1 증가시킵니다. count가 k에 도달하면 bouquets를 1 증가시키고 count를 0으로 초기화합니다.
- d > x이면 count를 0으로 초기화합니다. (꽃이 끊겨 연속된 꽃을 셀 수 없음)
마지막에 bouquets ≥ m이면 true, 그렇지 않으면 false를 반환합니다.

2. 이진 탐색으로 최소 일수 찾기

n := bloomDay의 크기를 구하고, m × k > n이면 꽃의 수가 부족하므로 -1을 반환합니다.
left := 0, right := max(bloomDay) + 1로 탐색 범위를 설정합니다.
left < right 동안 다음을 반복합니다.
- mid := (left + right) // 2
- possible(mid)가 true이면 right := mid (더 짧은 날짜에서도 가능한지 확인)
- false이면 left := mid + 1 (더 많이 기다려야 함)
반복이 끝난 후 possible(left)가 true이면 left를, 아니면 left + 1을 반환합니다.

파이썬 구현 코드

def solve(bloomDay, m, k):
    n = len(bloomDay)
    if m * k > n:
        return -1

    def possible(x):
        count = 0
        bouquets = 0
        for d in bloomDay:
            if d <= x:
                count += 1
                if count == k:
                    bouquets += 1
                    count = 0
            else:
                count = 0
        return bouquets >= m

    left, right = 0, max(bloomDay) + 1
    while left < right:
        mid = (left + right)//2
        if possible(mid):
            right = mid
        else:
            left = mid + 1

    if possible(left):
        return left
    else:
        return left + 1

bloomDay = [5,5,5,5,10,5,5]
m = 2
k = 3
print(solve(bloomDay, m, k))

입력

[5,5,5,5,10,5,5], 2, 3

출력

복잡도 분석

possible() 함수는 배열을 한 번 순회하므로 O(n)의 시간이 소요되며, 이진 탐색 과정에서 최대 O(log(max(bloomDay)))번 호출됩니다. 따라서 전체 시간 복잡도는 O(n · log(max(bloomDay)))이고, 별도의 저장 공간이 필요하지 않아 공간 복잡도는 O(1)입니다.