[Leetcode] 2598. Smallest Missing Non-negative Integer After Operations

MEX(minimum excluded) 라는 개념이 등장한다. 이 문제에서는 주어지는 정수배열에서 배열의 각 숫자들에 value 를 더하거나 빼서 만들 수 있는 음수가 아닌 숫자 중 가장 작은 숫자를 의미한다. 그리고 가장 큰 MEX 값을 반환하는 문제.

배열 내의 모든 숫자들을 0~value-1 의 숫자들로 만든 뒤 0부터 올라가면서 갯수만 세면 된다. 0부터 1씩 감소하므로 제일 먼저 값이 0이 되는 녀석을 만나면 반환한다.

function findSmallestInteger(nums: number[], value: number): number {
    const counter = new Map()

    nums.forEach(num => {
        const remainder = (num % value + value) % value;

        counter.set(remainder, (counter.get(remainder) || 0) + 1)
    })

    let mex = 0;

    while(true) {
        const target = mex % value;

        const count = counter.get(target) || 0;

        if (count > 0) {
            counter.set(target, count - 1);
            mex += 1
        } else {
            return mex;
        }
    }
};