연속 숫자(Sequential Digits)란?
연속 숫자를 가진 수란 숫자의 각 자릿수가 바로 앞의 자릿수보다 정확히 1만큼 큰 수를 의미합니다. 예를 들어 1234, 4567, 23456 같은 수가 대표적인 예입니다.
문제 정의
정확히 두 개의 요소로 이루어진 배열 arr을 입력받는 JavaScript 함수를 작성해야 합니다. 이 배열은 탐색할 숫자의 범위를 지정합니다.
함수는 해당 범위(경계값 포함) 안에 속한 모든 정수 중에서 연속 숫자를 가진 값들만 골라, 오름차순으로 정렬된 배열 형태로 반환해야 합니다.
예를 들어, 함수에 다음과 같은 입력값이 주어졌다고 가정해 보겠습니다.
const arr = [1000, 13000];
그렇다면 출력 결과는 다음과 같아야 합니다.
const output = [1234, 2345, 3456, 4567, 5678, 6789, 12345];
구현 코드
이 문제를 해결하는 전체 코드는 다음과 같습니다.
const arr = [1000, 13000];
const sequentialDigits = ([low, high] = [1, 1]) => {
const findCount = (num) => {
let count = 0;
while(num > 0){
count += 1
num = Math.floor(num / 10)
};
return count;
};
const helper = (count, start) => {
let res = start;
while(count > 1 && start < 9){
res = res * 10 + start + 1;
start += 1;
count -= 1;
};
if(count > 1){
return 0;
};
return res;
};
const count1 = findCount(low);
const count2 = findCount(high);
const res = [];
for(let i = count1; i <= count2; i++){
for(let start = 1; start <= 8; start++){
const num = helper(i, start);
if(num >= low && num <= high){
res.push(num);
};
};
};
return res;
};
console.log(sequentialDigits(arr));코드 동작 원리
이 코드는 세 단계로 동작합니다.
1. 자릿수 계산(findCount): 범위의 하한값(low)과 상한값(high)의 자릿수를 각각 계산합니다. 이를 통해 생성해야 할 숫자의 길이 범위를 파악할 수 있습니다.
2. 연속 숫자 생성(helper): 시작 자릿수(start)와 목표 자릿수(count)를 받아, 해당 조건에 맞는 연속 숫자를 만듭니다. 예를 들어 start가 1이고 count가 4이면 1234를 생성합니다. 만약 9를 넘어서까지 자릿수를 이어갈 수 없다면 0을 반환하여 유효하지 않음을 표시합니다.
3. 범위 검증 및 수집: 가능한 모든 자릿수와 시작 자릿수 조합에 대해 숫자를 생성한 뒤, 그 값이 주어진 범위 [low, high] 안에 속하는 경우에만 결과 배열에 추가합니다.
출력 결과
콘솔에 출력되는 최종 결과는 다음과 같습니다.
[ 1234, 2345, 3456, 4567, 5678, 6789, 12345 ]
이 접근 방식은 브루트포스 방식으로 범위 내 모든 숫자를 일일이 확인하는 것보다 훨씬 효율적입니다. 연속 숫자의 개수는 전체적으로 매우 제한적이기 때문입니다. 실제로 존재할 수 있는 연속 숫자는 12부터 123456789까지 총 36개뿐이므로, 필요한 숫자만 직접 생성하여 범위와 비교하는 방식이 시간 복잡도 면에서 큰 이점을 가집니다.