숫자 리스트 nums가 있다고 가정해 봅시다. 각 값은 함께 스카이다이빙을 하고자 하는 그룹의 인원수를 나타냅니다. 또 다른 값 k는 스카이다이빙을 신청할 수 있는 총 일수를 의미합니다. 우리의 목표는 k일 이내에 모든 요청을 처리할 수 있는 비행기의 최소 탑승 정원을 구하는 것입니다.
단, 두 가지 제약 조건이 있습니다.
- 요청은 주어진 순서대로 처리되어야 합니다.
- 비행기는 하루에 한 번만 운항할 수 있습니다.
예를 들어 입력이 nums = [16, 12, 18, 11, 13], k = 3이라면 출력은 28이 됩니다. 28인승 비행기를 사용하면 요청을 [16, 12], [18], [11, 13]처럼 3일에 걸쳐 나누어 처리할 수 있기 때문입니다.
접근 방법: 이진 탐색(Binary Search)
이 문제는 이진 탐색으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 비행기 용량의 최솟값은
nums중 가장 큰 값입니다. 어떤 그룹도 분리될 수 없기 때문입니다. - 용량의 최댓값은
nums의 모든 원소의 합입니다. 모든 그룹을 하루에 한 번에 태우는 경우입니다.
이 범위 사이에서 특정 용량으로 k일 이내에 모든 요청을 처리할 수 있는지 확인하며, 가능한 최소 용량을 찾아나갑니다.
알고리즘 단계
nums가 비어 있으면 0을 반환합니다.start:=nums의 최댓값,end:=nums의 모든 원소의 합으로 설정합니다.start < end인 동안 다음을 반복합니다.mid:= (start+end) // 2days:= 1,temp:= 0으로 초기화합니다.nums의 각num에 대해:temp + num > mid이면 새로운 날이 필요하므로days를 1 증가시키고temp:=num으로 설정합니다.- 그렇지 않으면
temp:=temp + num으로 누적합니다.
days > k이면 용량이 부족한 것이므로start:=mid + 1로 설정합니다.- 그렇지 않으면
end:=mid로 설정하여 더 작은 용량을 탐색합니다.
start를 반환합니다.
구현 예제
class Solution:
def solve(self, nums, k):
if not nums:
return 0
start, end = max(nums), sum(nums)
while start < end:
mid = (start + end) // 2
days = 1
temp = 0
for num in nums:
if temp + num > mid:
days += 1
temp = num
else:
temp += num
if days > k:
start = mid + 1
else:
end = mid
return start
ob = Solution()
nums = [16, 12, 18, 11, 13]
k = 3
print(ob.solve(nums, k))입력
[16, 12, 18, 11, 13], 3
출력
28
복잡도 분석
탐색 범위는 최대 sum(nums)까지이므로 이진 탐색에는 O(log S)번의 반복이 필요하고(S는 원소의 총합), 각 반복마다 리스트를 한 번 순회하므로 전체 시간 복잡도는 O(n log S)입니다. 공간 복잡도는 추가 배열 없이 상수 변수만 사용하므로 O(1)입니다.