[LeetCode] 813. Largest Sum of Averages

Chobby·2026년 10월 1일

JavaScript js ts typescript 기술 기초 면접 문제 알고리즘 연습 이직 코딩 코테 풀이 프로그래밍

LeetCode

목록 보기

1154/1156

문제

정수 배열 nums를 최대 k개의 인접한 부분배열로 나눈다. 점수는 각 부분배열 평균의 합이다. 얻을 수 있는 최대 점수를 구하는 문제다.

모든 원소를 빠짐없이 사용해야 한다.
부분배열은 연속 구간이어야 한다. 원소 순서는 바꿀 수 없다.

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
설명: [9], [1,2,3], [9] → 9 + 2 + 9 = 20

첫 번째 시도: 정렬 + 그리디 (오답)

"큰 수는 혼자 한 조각으로 두고 나머지는 한 덩어리로 평균 내면 최대가 되지 않을까?"라는 생각으로 처음 풀이를 짰다.

function largestSumOfAverages(nums: number[], k: number): number {
    const desc = nums.toSorted((a, b) => b - a);
    const group: number[] = [];
    for (let i = 0; group.length < k - 1; i++) {
        group.push(desc[i]);
    }
    const remain = desc.slice(k - group.length + 1);
    const remainSum = remain.reduce((acc, cur) => acc + cur, 0);
    const avg = remainSum / remain.length;
    group.push(avg);
    const groupSum = group.reduce((acc, cur) => acc + cur, 0);

    return groupSum
};

nums = [1,2,3,4,5,6,7], k = 4에서 정답은 20.5인데 이 코드는 21을 반환했다.

문제점 1. slice 인덱스 버그

group = [7,6,5]일 때 slice(k - group.length + 1)은 slice(2)가 된다. 그러면 remain이 [5,4,3,2,1]이 되어 5가 두 번 계산된다.

slice(k - 1)로 고치면 7 + 6 + 5 + avg(4,3,2,1) = 20.5로 예제는 통과한다. 하지만 이 예제는 입력이 이미 정렬돼 있어서 우연히 맞은 것이다.

문제점 2. 정렬하면 안 되는 문제

조각은 연속 구간이어야 한다. 정렬해서 큰 수만 골라내는 건 원래 배열에서 불가능한 분할이다.

nums = [1,9,1,9,1], k = 2

그리디: 9 + avg(9,1,1,1) = 12   ← 실제로 만들 수 없는 분할
정답:   [1,9] | [1,9,1] = 5 + 3.67 ≈ 8.67

핵심 아이디어: 첫 조각을 어디서 자를까?

모든 분할을 직접 다 따지는 대신 첫 번째 조각의 끝 위치만 정한다.

nums = [1,9,1,9,1], k = 2

[1]       | [9,1,9,1]  →  1    + 5    = 6
[1,9]     | [1,9,1]    →  5    + 3.67 = 8.67  ← 최대
[1,9,1]   | [9,1]      →  3.67 + 5    = 8.67
[1,9,1,9] | [1]        →  5    + 1    = 6

첫 조각을 정하고 나면, 남은 일은 나머지 배열을 k - 1조각으로 자르는 같은 모양의 문제다. 그래서 재귀로 풀 수 있다.

종료 조건: 1조각만 남으면 남은 원소 전체의 평균을 반환한다.
점화식: partition(start, k) = max(avg(start..end) + partition(end, k - 1))
메모이제이션: 같은 (start, k) 조합이 여러 번 나오므로 결과를 저장해 둔다.

풀이 코드

const avg = (nums: number[]) => nums.reduce((acc, cur) => acc + cur, 0) / nums.length;
function largestSumOfAverages(nums: number[], k: number): number {
    const n = nums.length;

    const memo = new Map<string, number>();
    const partition = (start: number, remainK: number) => {
        if (remainK === 1) return avg(nums.slice(start));
        
        const key = `${start},${remainK}`;
        if (memo.has(key)) return memo.get(key);

        let max = 0
        for(let end = start + 1; end < n; end++) {
            const curAvg = avg(nums.slice(start, end));
            max = Math.max(max, curAvg + partition(end, remainK - 1));
        }

        memo.set(key, max);
        return max;
    }

    return partition(0, k);
};

end < n 조건 덕분에 첫 조각 뒤에 최소 1개 원소가 항상 남는다.
상태는 (start, remainK) 조합으로 n × k개다.

복잡도

시간: O(k · n³). 상태 n × k개마다 end를 n번 돌고, 매번 slice + reduce로 O(n)을 쓴다.
공간: O(n · k). 메모 크기다.

n ≤ 100이라 이대로도 통과한다. 누적합(prefix sum)을 쓰면 구간 평균을 O(1)에 구할 수 있어서 O(k · n²)까지 줄일 수 있다.

const prefix = [0];
for (const x of nums) prefix.push(prefix.at(-1)! + x);
const rangeAvg = (i: number, j: number) => (prefix[j] - prefix[i]) / (j - i);