자바스크립트(JavaScript)로 n자리 숫자 중 자릿수가 모두 고유한 수의 개수 구하기

이번 글에서는 하나의 숫자를 인수로 받아, 해당 숫자만큼의 자릿수를 가지면서 모든 자릿수가 서로 중복되지 않는 고유한 숫자의 개수를 세는 자바스크립트 함수를 만들어 보겠습니다.

문제 정의

함수는 num이라는 숫자 하나를 유일한 인수로 받습니다. 그리고 num자리 숫자들 중에서 각 자릿수가 모두 서로 다른 숫자들의 총 개수를 반환해야 합니다.

예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 봅시다.

const num = 1;

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

const output = 10;

출력 설명

1자리 숫자인 0, 1, 2, 3, 4, 5, 6, 7, 8, 9는 모두 한 자릿수이며 각 숫자가 단 한 번만 등장하기 때문에, 조건을 만족하는 숫자는 총 10개입니다.

구현 예제 코드

다음은 동적 계획법(Dynamic Programming)을 활용해 이 문제를 해결한 코드입니다.

const num = 1;
const uniqueDigits = (num = 1) => {
    const dp = [1, 10];
    const sum = [1, 11];
    for (let i = 2; i <= num; i++) {
        dp[i] = sum[i - 1] + (10 - i) * (dp[i - 1]);
        sum[i] = sum[i - 1] + dp[i];
    };
    return dp[num];
};
console.log(uniqueDigits(num));
console.log(uniqueDigits(2));
console.log(uniqueDigits(3));

코드 설명

이 코드의 핵심은 동적 계획법(Dynamic Programming)입니다. 두 개의 배열을 사용하여 원하는 값을 효율적으로 추적합니다.

dp 배열

dp[i]는 정확히 i자리이면서 모든 자릿수가 고유한 숫자의 개수를 저장합니다. 첫 번째 항목은 0자리를 나타내기 위한 기본값 1이고, 두 번째 항목 10은 1자리 숫자의 개수(0~9)입니다.

sum 배열

sum[i]는 1자리부터 i자리까지의 고유 숫자 개수를 모두 더한 누적합입니다. 이전 단계의 결과를 재활용하므로 불필요한 반복 계산 없이 빠르게 답을 구할 수 있습니다.

점화식의 원리

i자리 고유 숫자는 (i-1)자리 이하의 모든 고유 숫자 앞에 새로운 자릿수를 추가하는 방식으로 만들어집니다. 이때 이미 사용된 숫자를 제외하고 선택할 수 있는 숫자는 (10 - i)개이므로, 점화식은 다음과 같이 구성됩니다.

dp[i] = sum[i - 1] + (10 - i) * dp[i - 1];

즉, 이전까지의 모든 경우(sum[i - 1])에 새 자릿수를 붙이는 경우와, 정확히 (i-1)자리 고유 숫자에 남은 숫자 중 하나를 추가하는 경우를 합산합니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 출력이 나타납니다.

10
91
739

결과를 살펴보면, 1자리 고유 숫자는 10개, 2자리 고유 숫자는 91개, 3자리 고유 숫자는 739개입니다. 참고로 완전 탐색(Brute Force)으로 이 문제를 풀면 입력이 커질 때 성능이 급격히 저하되지만, 동적 계획법을 사용하면 선형 시간(O(n)) 안에 효율적으로 답을 구할 수 있다는 장점이 있습니다.