[Leetcode] 3397. Maximum Number of Distinct Elements After Operations

정수로 된 배열 nums 이 주어지고 정수 k 가 주어진다. 배열의 각 원소들에 -k ~ k 를 더할 수 있다. 이 때 배열의 모든 원소가 최대한 고유하도록 만들고 고유한 원소의 개수를 세는 문제.

원소들은 범위의 값을 가진다고 가정하고 이 범위값을 얼마나 채울 수 있는지는 원소의 개수가 정한다. 원래 nums 배열을 한번 정렬하는 과정이 필요하지만 나는 Object.entries() 로 변환하면서 자동으로 정렬시켰다. 들어가는 범위값의 원소는 Set() 으로 관리하고 .size 를 재면 된다.

하나의 원소의 범위값을 산정하고 다음 원소로 넘어갈 때 currentValue 를 결정하는 과정에서 이전 원소가 현재 원소의 범위값을 침범하는 경우를 대비해 Math.max(prevValue, numKey - k) 로 시작값을 조정해주어야 더욱 효율적으로 돌 수 있다. 실제로 이 코드를 추가하기 전에는 시간초과가 떴었다.

function maxDistinctElements(nums: number[], k: number): number {
    const numSet = new Set()

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

        return acc
    }, {})

    let prevValue = 0

    Object.entries(numDict).forEach(([key, value], index) => {
        let count = Number(value)
        const numKey = Number(key)
        let currentValue = numKey - k
        
        if (index !== 0) {
            currentValue = Math.max(prevValue, numKey - k)
        } 

        while (count > 0) {
            if (numSet.has(currentValue)) {
                currentValue += 1
                prevValue = currentValue 
            } else {
                numSet.add(currentValue)
                count -= 1
            }

            if (currentValue > numKey + k) {
                break;
            }
        }
    })

    return numSet.size
};

통과는 했으나 백분위가 상당히 참담하다.... 오늘은 할 일이 많아 최적화는 다음에 진행하자..