JavaScript로 아름다운 숫자 문자열 판별하기

아름다운(beautiful) 문자열이란?

숫자 문자열 str이 두 개 이상의 양의 정수로 이루어진 수열 arr로 분할될 수 있고, 다음 조건들을 모두 만족한다면 이를 아름다운 문자열이라고 합니다.

arr[i] - arr[i - 1] = 1: 수열의 모든 인덱스 i에 대해 각 요소는 바로 앞 요소보다 정확히 1만큼 커야 합니다.
수열의 어떤 요소도 선행 0(leading zero)을 포함해서는 안 됩니다. 예를 들어 '50607'은 [5, 06, 07]로 분할할 수 있지만, 06과 07에 선행 0이 존재하므로 아름다운 문자열이 아닙니다.
분할된 수열의 내용은 임의로 재배열할 수 없습니다.

예시

입력 문자열이 다음과 같다고 가정해 보겠습니다.

const str = '91011';

이때 기대하는 출력 결과는 다음과 같습니다.

const output = true;

그 이유는 이 문자열을 원하는 수열인 [9, 10, 11]로 분할할 수 있기 때문입니다.

구현 코드

위 조건을 검증하는 코드는 다음과 같습니다.

const str = '91011';
const isBeautiful = (str) => {
    let i = 1;
    let count=0;
    const { length } = str;
    while(i <= length / 2){
        let check = true;
        let j = i;
        let left = BigInt(str.substring(0,j));
        let nextRange = (left + 1n).toString().length;
        while(j + nextRange <= length){
            let right=BigInt(str.substring(j,j+nextRange));
            if(left === right-1n){
                left=right;
                j+=nextRange;
                nextRange=(left+1n).toString().length;
                count=j;
            }else{
                check=false;
                break;
            }
        };
        if(check === true && count === length){
            return true;
        }
        i++;
    };
    return false;
};
console.log(isBeautiful(str));

동작 원리

이 알고리즘은 다음과 같은 단계로 동작합니다.

첫 번째 숫자가 될 수 있는 길이를 1부터 문자열 길이의 절반까지 하나씩 시도합니다. 첫 숫자가 전체의 절반보다 길면 뒤에 올 숫자가 존재할 수 없기 때문입니다.
첫 숫자를 기준으로, 그다음 숫자는 항상 1이 큰 값이므로 자릿수를 미리 계산하여 문자열에서 해당 구간을 잘라냅니다.
BigInt를 사용하기 때문에 일반적인 Number 범위를 초과하는 매우 큰 숫자 문자열도 안전하게 처리할 수 있습니다.
모든 분할 과정에서 연속성이 유지되고 문자열 끝까지 정확히 도달했다면 true를 반환하고, 그렇지 않으면 다음 후보 길이를 시도합니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true