숫자로 이루어진 리스트 nums와 정수 k가 주어졌다고 가정해 봅시다. 이 리스트를 k개의 연속된(contiguous) 그룹으로 나누려고 합니다. 여기서 '가장 작은 그룹'은 모든 그룹 중에서 원소의 합이 가장 작은 그룹을 의미하며, 우리의 목표는 이 최소 그룹의 합이 가질 수 있는 최댓값을 구하는 것입니다.
문제 이해하기
예를 들어 입력이 nums = [2, 6, 4, 5, 8], k = 3이라면 출력은 8이 됩니다. 리스트를 [2, 6], [4, 5], [8]처럼 세 그룹으로 나눌 수 있고, 각 그룹의 합은 8, 9, 8이므로 가장 작은 그룹의 합은 8이 됩니다. 어떻게 나누더라도 최소 그룹의 합이 8보다 커지도록 만들 수 없기 때문에 정답은 8입니다.
접근 방법: 이진 탐색(매개변수 탐색)
이 문제는 이진 탐색(binary search)으로 효율적으로 해결할 수 있습니다. "최소 그룹의 합이 target 이상이 되도록 k개의 그룹으로 나눌 수 있는가?"라는 판별 함수를 정의한 뒤, 답이 될 수 있는 범위에서 이진 탐색을 수행하는 방식입니다.
판별 함수는 그리디(greedy)하게 동작합니다. 리스트를 왼쪽부터 순회하면서 누적합이 target 이상이 되는 순간 그룹을 하나 확정하는 것입니다. 이렇게 만들어진 그룹의 개수가 k에 도달하는지만 확인하면 됩니다.
알고리즘 단계
- is_divisible(target) 함수를 정의합니다. 합이 target 이상인 그룹을 k개 만들 수 있으면 True를 반환합니다.
- target이 1 이하이면 항상 조건을 만족하므로 True를 반환합니다.
num_chunks = 0,current_sum = 0으로 초기화합니다.- nums의 각 원소 x에 대해 다음을 반복합니다.
current_sum += xcurrent_sum >= target이면current_sum = 0으로 초기화하고num_chunks += 1을 수행합니다. 만약num_chunks == k라면 True를 반환합니다.
- 반복을 마치면 False를 반환합니다.
- 메인 메서드에서는
left = 1,right = sum(nums) // k + 1로 설정합니다. left < right - 1인 동안mid = (left + right) // 2를 계산하여,is_divisible(mid)가 참이면left = mid, 거짓이면right = mid로 갱신합니다.- 마지막으로
left를 반환합니다. 이것이 바로 최소 그룹 합의 최댓값입니다.
파이썬 구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution: def solve(self, nums, k): def is_divisible(target): if target <= 1: return True num_chunks = 0 current_sum = 0 for x in nums: current_sum += x if current_sum >= target: current_sum = 0 num_chunks += 1 if num_chunks == k: return True return False left = 1 right = sum(nums) // k + 1 while left < right - 1: mid = (left + right) // 2 if is_divisible(mid): left = mid else: right = mid return left ob = Solution() nums = [2, 6, 4, 5, 8] k = 3 print(ob.solve(nums, k))
입력
[2, 6, 4, 5, 8], 3
출력
8
시간 복잡도
판별 함수 한 번 호출에 O(n)의 시간이 걸리고, 이진 탐색은 O(log(sum(nums)))번 반복됩니다. 따라서 전체 시간 복잡도는 O(n log(sum(nums)))이며, 가능한 모든 분할 방법을 일일이 확인하는 완전 탐색보다 훨씬 효율적입니다.