음이 아닌 정수 n이 주어졌을 때, 0부터 10^n 범위 안에서 모든 자릿수가 서로 다른(중복되지 않는) 숫자 x의 개수를 구하는 문제입니다.
예를 들어 n이 2라면, 구해야 할 범위는 0부터 100까지입니다. 이때 11, 22, 33, 44, 55, 66, 77, 88, 99처럼 같은 숫자가 반복되는 수는 제외해야 하므로, 결과값은 91이 됩니다.
문제 해결 접근 방법
이 문제는 수학적 규칙을 활용하면 효율적으로 풀 수 있습니다. 각 단계는 다음과 같습니다.
- n이 0이면, 표현할 수 있는 숫자는 0 하나뿐이므로 1을 반환합니다.
- n의 값이 10보다 크면 의미가 없으므로, n을 10과 n 중 작은 값으로 설정합니다. (10자리 이상이면 어떤 숫자든 반드시 중복된 자릿수가 존재하기 때문입니다.)
- n이 1이면 0부터 9까지 모두 조건을 만족하므로 10을 반환합니다.
- ans := 9, ret := 10으로 초기화합니다. 첫 번째 자리에는 0을 제외한 9가지 선택이 가능하고, 한 자리 숫자는 모두 조건을 만족하기 때문입니다.
- i가 2부터 n까지일 때 다음을 반복합니다.
- ans := ans * (9 - i + 2) — 새로운 자릿수를 추가할 때 사용 가능한 숫자의 가짓수를 곱합니다.
- ret := ret + ans — 해당 자릿수 길이에서 만들 수 있는 유효한 숫자의 개수를 누적합니다.
- 최종적으로 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(n == 0)return 1;
n = min(10, n);
if(n == 1)return 10;
int ans = 9;
int ret = 10;
for(int i = 2; i<= n; i++){
ans *= (9 - i + 2);
ret += ans;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.countNumbersWithUniqueDigits(3));
}입력
3
출력
739
결과 분석
n이 3인 경우, 0부터 1000 사이에서 자릿수가 모두 다른 숫자의 개수는 739개입니다. 세 자리 숫자의 경우 첫째 자리에 9가지(1~9), 둘째 자리에 9가지(0 포함, 첫째 자리 제외), 셋째 자리에 8가지를 선택할 수 있어 9 × 9 × 8 = 648개가 되고, 여기에 한 자리 숫자 10개와 두 자리 숫자 81개를 더하면 739가 됩니다.
이 알고리즘은 반복문을 최대 10번만 수행하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.