문제 소개
숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 길이가 k 이상인 연속된 하위 리스트 중에서 가장 큰 평균값을 찾는 프로그램을 만들어 보겠습니다.
예를 들어 입력이 nums = [2, 10, -50, 4, 6, 6], k = 3이라면 결과는 5.33333333이 됩니다. 하위 리스트 [4, 6, 6]의 평균값이 가장 크기 때문입니다.
접근 방법: 답에 대한 이진 탐색
모든 가능한 하위 리스트를 일일이 확인하는 것은 매우 비효율적입니다. 대신 답에 대한 이진 탐색(Binary Search on Answer) 기법을 활용하면 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 평균값은 항상 리스트의 최솟값과 최댓값 사이에 존재하므로, 이 범위 안에서 특정 값 mid 이상의 평균을 가지는 하위 리스트가 존재하는지 검사하고, 조건에 따라 탐색 범위를 절반씩 줄여 나가면 최대 평균을 빠르게 좁혀 나갈 수 있습니다.
알고리즘 단계
다음 순서로 문제를 해결합니다.
left는 nums의 최솟값,right는 nums의 최댓값으로 초기화합니다.s는 nums의 첫 k개 원소(인덱스 0부터 k-1까지)의 합으로 설정합니다.largest_avg를 s / k로 초기화합니다.left <= right인 동안 다음을 반복합니다.mid:= (left + right) / 2의 정수 부분sum1:= s,avg:= s / k,sum2:= 0,cnt:= 0으로 초기화합니다.- i를 k부터 nums의 길이까지 순회하면서:
sum1에 nums[i]를 더합니다.sum2에 nums[i - k]를 더합니다.cnt를 1 증가시킵니다.avg를 avg와 sum1 / (cnt + k) 중 더 큰 값으로 갱신합니다.- 만약 sum2 / cnt <= mid라면, sum1에서 sum2를 빼고 cnt와 sum2를 0으로 초기화합니다.
avg를 다시 한 번 avg와 sum1 / (cnt + k) 중 더 큰 값으로 갱신합니다.
largest_avg를 largest_avg와 avg 중 더 큰 값으로 갱신합니다.- avg > mid이면
left:= mid + 1, 그렇지 않으면right:= mid - 1로 설정합니다.
largest_avg를 반환합니다.
Python 구현 코드
아래 코드를 통해 실제 구현 과정을 확인할 수 있습니다.
class Solution:
def solve(self, nums, k):
left, right = min(nums), max(nums)
s = sum(nums[:k])
largest_avg = s / k
while left <= right:
mid = (left + right) // 2
sum1 = s
avg = s / k
sum2 = 0
cnt = 0
for i in range(k, len(nums)):
sum1 += nums[i]
sum2 += nums[i - k]
cnt += 1
avg = max(avg, sum1 / (cnt + k))
if sum2 / cnt <= mid:
sum1 -= sum2
cnt = 0
sum2 = 0
avg = max(avg, sum1 / (cnt + k))
largest_avg = max(largest_avg, avg)
if avg > mid:
left = mid + 1
else:
right = mid - 1
return largest_avg
ob = Solution()
nums = [2, 10, -50, 4, 6, 6]
k = 3
print(ob.solve(nums, k))
입력
[2, 10, -50, 4, 6, 6], k = 3
출력
5.333333333333333
시간 복잡도 분석
이 알고리즘은 이진 탐색을 O(log(max - min))번 수행하고, 각 탐색마다 리스트를 한 번씩 순회하므로 전체 시간 복잡도는 O(n log(max - min))입니다. 모든 하위 리스트를 하나씩 확인하는 브루트 포스 방식(O(n²) 이상)보다 훨씬 효율적이며, 리스트의 크기가 커져도 안정적인 성능을 유지할 수 있습니다.