[Leetcode] 2048. Next Greater Numerically Balanced Number

주어진 수 보다 큰 수 중에 가장 작은 Balanced 한 숫자를 반환하는 문제. Balanced 란 수를 구성하는 모든 한자리 숫자 a 가 a 번 나오는 숫자를 의미한다(ex: 1, 22, 1333, 122333 등).

먼저 숫자의 자릿수를 구해 만들어야 하는 Balanced Number 의 자릿수를 구한다. 여기서 한자릿수 숫자는 22 로 early return 이 나오니 보내버린다. 그리고 퍼뮤테이션을 돌려서 값을 비교한다. 주의할 점이라면 자릿수가 커질 때 큰 자릿수의 숫자는 다시 작은 자릿수로 쪼개질 수 있어서 재귀함수를 사용해 모든 경우의 수를 구해줬다.

function nextBeautifulNumber(n: number): number {
    const nString: string = n.toString()

    let targetLength: number = nString.length

    if (n >= Number(targetLength.toString().repeat(targetLength))) {
        targetLength += 1

        // 두자릿수면 바로 리턴해도 됨
        if (targetLength === 2) {
            return 22
        }
    }

    // 일반적인 케이스 진행
    const getPossibleCases = (targetLen: number) => {
        const _possibleCases = []
        for (let i = 1; i <= Math.floor(targetLen / 2); i++) {
            const j = targetLen - i
            if (j !== i) {
                _possibleCases.push([i, j])
            }

            if (j >= 3) {
                const result = getPossibleCases(j)

                result.forEach(r => {
                    const t = [i, ...r]
                    
                    let isUnique = true
                    let tMap = new Map()
                    t.forEach(el => {
                        if (tMap.get(el)) {
                            isUnique = false
                        } else {
                            tMap.set(el, true)
                        }
                    })

                    if (isUnique) {
                        _possibleCases.push(t)
                    }
                })
            }
        }

        return _possibleCases
    }

    const possibleCases = getPossibleCases(targetLength)

    possibleCases.push([targetLength, 0])

    let answer = 7777777;

    for (const possibleCase of possibleCases) {
        const p = []

        for (let i of possibleCase) {
            const originalI = i
            while (i > 0) {
                p.push(originalI)
                i--;
            }
        }

        const permute = (arr, m = []) => {
            if (arr.length === 0) {
                const result = Number(m.join(''))
                if (result > n) {
                    answer = Math.min(answer, result)
                }
            } else {
                for (let i = 0; i < arr.length; i++) {
                    let cur = [...arr]
                    let next = cur.splice(i, 1);
                    permute(cur.slice(), m.concat(next))
                }
            }
        }

        permute(p)
    }

    return answer;
}