JavaScript로 길이가 지정된 연속 하위 배열의 최대 평균 구하기

문제 이해

정수 배열 arr을 첫 번째 인수로, 숫자 num을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 길이가 정확히 num인 연속된 하위 배열(subarray) 중에서 평균값이 가장 큰 것을 찾아, 그 최대 평균값을 반환해야 합니다.

예를 들어 함수의 입력이 다음과 같다면,

입력

const arr = [1, 12, -5, -6, 50, 3];
const num = 4;

출력

const output = 12.75;

출력 설명

우리가 찾아야 하는 하위 배열은 [12, -5, -6, 50]입니다. 이 배열의 합은 51이며, 평균은 51 ÷ 4 = 12.75가 됩니다.

접근 방법: 슬라이딩 윈도우 기법

가능한 모든 하위 배열마다 매번 합을 새로 계산하는 브루트 포스 방식은 비효율적입니다. 대신 슬라이딩 윈도우(Sliding Window) 기법을 사용하면 배열을 한 번만 순회해서 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

• 먼저 첫 num개 요소의 합을 구합니다.
• 윈도우를 오른쪽으로 한 칸씩 이동할 때, 새로 들어오는 요소(arr[i + num - 1])는 더하고, 빠져나가는 요소(arr[i - 1])는 뺍니다.
• 매 단계에서 현재 합과 지금까지의 최댓값을 비교하여 갱신합니다.
• 최종적으로 최대 합을 num으로 나누면 최대 평균값이 됩니다.

예제 코드

다음은 위 로직을 구현한 코드입니다.

const arr = [1, 12, -5, -6, 50, 3];
const num = 4;
const maxAverage = (arr = [], num) => {
    let sum = arr.slice(0, num).reduce((acc, v) => acc + v, 0)
    let max = sum
    for (let i = 1; i <= arr.length - num; i++) {
        sum = sum + arr[i + num - 1] - arr[i - 1]
        max = Math.max(max, sum)
    }
    return max / num
}
console.log(maxAverage(arr, num));

출력 결과

12.75

시간 복잡도 분석

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리 사용 없이 몇 개의 변수만 활용하므로 공간 복잡도는 O(1)입니다. 모든 경우를 일일이 검사하는 브루트 포스 방식(O(n × num))에 비해 훨씬 효율적이며, 배열의 크기가 커질수록 그 차이가 더욱 두드러집니다.