[Leetcode] 3005. Count Elements With Maximum Frequency

양의 정수로 이루어진 배열이 있고, 여기서 가장 많은 빈도수로 나온 숫자들의 개수의 합을 구하는 문제. 처음에는 머릿속에 떠오르는 대로 풀어봤다.

function maxFrequencyElements(nums: number[]): number {
    let maxNum = 0

    const numDict = nums.reduce((acc, cur) => {
        if (acc[cur] == null) {
            acc[cur] = 1
        } else {
            acc[cur] += 1
        }

        if (acc[cur] > maxNum) {
            maxNum = acc[cur]
        }

        return acc
    }, {})

    return nums.reduce((acc, cur) => {
        if (numDict[cur] === maxNum) {
            return acc + 1
        }

        return acc
    }, 0)
};

그러나 상위 94%라는 기적적인 실행시간(와!9등급!!)을 보고 개선이 필요하겠구나 싶었다.

시간복잡도는 O(N) 이라 딱히 문제가 되진 않고, 배열을 두 번 도는 걸 한 번만 돌게 만들면 되지 않을까? .reduce() 안에서 한번에 해결할 수 있겠다는 생각이 들었다.

function maxFrequencyElements(nums: number[]): number {
    const dict = new Map()
    let maxFreq = 0

    return nums.reduce((acc, cur) => {
        const currentFreq = (dict.get(cur) ?? 0) + 1;
        dict.set(cur, currentFreq)

        if (currentFreq > maxFreq) {
            maxFreq = currentFreq
            return currentFreq
        }

        if (currentFreq === maxFreq) {
            return acc + currentFreq
        }

        return acc
    }, 0)
};

최댓값과 동일한 값을 가지는 순간과 최댓값을 넘어서는 순간의 frequency 를 조절하며 한 번만 순회하도록 했더니 바로 상위 0퍼센트(와!1등급!!) 이 되어버렸다.