[Leetcode] 3346. Maximum Frequency of an Element After Performing Operations I

배열의 원소 중 n 개를 [-k ~ k] 범위로 수정할 수 있을때 최대빈도수로 나올 수 있는 빈도수를 구하는 문제. 한 원소는 한 번만 수정될 수 있으며 총 numOperations 번만 수정이 가능하다는 제약이 있다.

구간합을 미리 구해놓고 배열의 최소값부터 최대값까지의 모든 값에 대해 얼마나 많은 다른 원소들을 해당 원소로 변환시킬 수 있을지 구하면 된다.

먼저 빈도수 counts 를 만들고 구간합 prefixSum 를 만든다. 타자 치기 귀찮아서 점점 변수명이 짧아진다

이후 tail, head 로 구간을 잡고 해당 범위 내 변환 가능한 값들을 찾는다. 그 값들이 numOperations 보다 큰지 비교해서 정답과 비교해나가면 된다. 구간합을 통해 얻을 수 있는 것은 범위 내 변환 가능한 모든 값들의 개수임을 이해하면 끝.

function maxFrequency(nums: number[], k: number, numOperations: number): number {
    nums.sort((a, b) => a - b)
    const counts = new Array(Math.max(...nums) + 1 + k).fill(0)

    for (let i = 0; i < nums.length; i++) {
        counts[nums[i]] += 1;
    }

    const p = [counts[0]]; //prefix sum

    for (let i = 1; i < counts.length; i++) {
        p[i] = p[i - 1] + counts[i];
    }

    let answer = 0;

    for (let i = 0; i < counts.length - k; i++) {
        let target = counts[i];

        let tail = Math.max(0, i - k - 1);
        let head = Math.min(p.length - 1, i + k);

        const availableAmount = p[head] - p[tail] - target;

        if (availableAmount > numOperations) {
            answer = Math.max(answer, target + numOperations);
        } else {
            answer = Math.max(answer, target + availableAmount);
        }
    }

    return answer
};