[Leetcode] 3347. Maximum Frequency of an Element After Performing Operations II

어제 푼 문제의 연장선이다. 모든 연산을 수행해야 하지만 numOperations <= nums.length 이기 때문에 사실상 의미가 없는 조건이다. 대신 constraints 가 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 0 <= k <= 10^9 로 자비없이 주어졌다. 어제처럼 Math.max(...nums) + k 로 배열을 선언하면 바로 시간초과가 나버린다.

그래서 Map, Set, Object 를 사용해서 비어있는 공간을 없앴다. 먼저 counts 는 Map 으로 선언하고 pSum 을 만들어서 값이 있는 원소에 대해서만 누적합을 더해놓는다(counts.keys()는 자동으로 정렬됨). 이후 구간합을 구해야 하는데 이 때는 disctinct 한 값들로 구성된 배열을 돌아야 하기 때문에 logN 의 시간을 얻기 위해 이진탐색을 사용한다.

이후 -k 와 k 값 까지 포함한 임계점을 설정한 Set 을 만든 뒤 구간합을 구했다.

function maxFrequency(nums: number[], k: number, numOperations: number): number {
    const counts = new Map<number, number>()

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

    const distinctNums = Array.from(counts.keys()).sort((a, b) => a - b)

    const pSum: { num: number, psum: number}[] = []
    let currentSum = 0
    for (const num of distinctNums) {
        currentSum += counts.get(num) ?? 0
        pSum.push({ num: num, psum: currentSum })
    }

    const queryPsum = (val: number) => {
        if (pSum.length === 0) {
            return 0
        }

        let answer = 0

        let l = 0
        let r = pSum.length - 1

        while(r >= l) {
            const mid = Math.floor((r + l) / 2)

            if (pSum[mid].num <= val) {
                answer = pSum[mid].psum
                l = mid + 1
            } else {
                r = mid - 1
            }
        }

        return answer;
    }

    const rangeSum = (L: number, R: number) => {
        if (L > R) {
            return 0;
        }

        return queryPsum(R) - queryPsum(L - 1)
    }

    const criticalPoints = new Set();
    for (const num of distinctNums) {
        criticalPoints.add(num)
        criticalPoints.add(num + k)
        criticalPoints.add(num - k)
    }

    let finalAnswer = 0
    for (const cpp of criticalPoints) {
        const cp = Number(cpp)
        if (cp < 0) {
            continue
        }

        const mid = counts.get(cp) ?? 0;
        const totalWindow = rangeSum(cp - k, cp + k)
        const availableAmount =  totalWindow - mid

        const freq = mid + Math.min(availableAmount, numOperations)
        
        finalAnswer = Math.max(finalAnswer, freq)
    }

    return finalAnswer
};