[Leetcode] 1838. Frequency of the Most Frequent Element

낮에 푼 Maximum Frequrency 와 비슷한 문제로 leetcode 가 추천해줘서 풀어본 문제. 이 문제는 더할 수 있는 량 k 를 주고 배열의 각 원소들에 나눠서 더할 수 있다.

먼저 갯수별 분포인 counts 배열을 만들고 각 숫자에서 배열의 뒤쪽을 바라보며 거리 * 갯수 로 availableAmount 를 찾는다. 이후 주어진 k 값 만큼 사용이 가능한지 판별을 하며 나아가도록 했다.

실행시간이 박살난 것은 배열의 index 를 한 칸씩 전진시키면서 뒤쪽을 for 문으로 순회했기 때문으로 보인다. 일단 코딩테스트가 있어 이 코드의 최적화는 다음 기회에..

function maxFrequency(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);

    const counts = Array(Math.max(...nums) + 1).fill(0);

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

    let answer = 0;

    let index = 1;
    while (index < counts.length) {
        let currentK = k;
        let left = Math.max(0, index - k);

        if (counts[index] === 0) {
            index += 1;
            continue;
        }

        let currentValue = counts[index]

        for (let i = index - 1; i >= left; i--) {
            const availableAmount = (index - i) * counts[i]
            
            if (currentK > availableAmount) {
                currentK -= availableAmount
                currentValue += counts[i]
            } else {
                currentValue += Math.floor(currentK / (index - i))
                break;
            }
        }

        answer = Math.max(answer, currentValue)
        index += 1
    }

    return answer
};