문제 개요
양의 정수 N이 주어졌을 때, 1부터 N 사이(양 끝값 포함)의 정수 중 최소 한 개 이상의 반복되는 자릿수를 가진 수의 개수를 구하는 것이 목표입니다.
예를 들어 입력이 99라면 출력은 9가 됩니다. 11, 22, 33, 44, 55, 66, 77, 88, 99처럼 같은 숫자가 두 번 이상 등장하는 수가 정확히 9개이기 때문입니다.
접근 방식
반복되는 자릿수를 가진 수를 직접 세는 것보다, 그 반대인 '모든 자릿수가 서로 다른 수'의 개수를 먼저 계산한 뒤 N에서 빼는 방식이 훨씬 효율적입니다. 서로 다른 자릿수로 이루어진 k자리 수의 개수는 순열(permutation) 공식으로 구할 수 있기 때문입니다.
알고리즘 단계
- A(m, n) 함수 정의: ret을 1로 초기화한 뒤, i가 0부터 n-1이 될 때까지 ret에 m을 곱하고 m을 1씩 감소시킵니다. 즉, m × (m−1) × … × (m−n+1) 값을 반환하는 순열 계산 함수입니다.
- 자릿수 분해: 배열 arr을 선언하고, i를 N+1부터 시작해 i가 0보다 클 동안 i를 10으로 나누어 가며 각 자릿수(i mod 10)를 arr의 앞쪽에 삽입합니다.
- 짧은 자릿수 처리: ret을 0으로 초기화하고 n을 arr의 크기로 설정한 뒤, i가 1부터 n-1일 때까지 ret에 9 × A(9, i−1)를 더합니다. 이는 i자리 수 중 중복 없는 수의 개수를 누적하는 과정입니다.
- N과 같은 길이의 수 처리: 집합 visited를 선언하고, i가 0부터 n-1일 때까지 다음을 반복합니다.
- digit := arr[i]로 현재 자릿수를 가져옵니다.
- j를 (i가 0이면 1, 아니면 0)부터 digit 미만까지 반복하면서, j가 visited에 이미 있다면 건너뛰고, 그렇지 않으면 ret에 A(9 − i, n − i − 1)를 더합니다.
- digit이 visited에 이미 존재하면 반복문을 종료하고, 그렇지 않으면 digit을 visited에 추가합니다.
- 결과 반환: 최종적으로 N − ret을 반환하면, 반복되는 자릿수를 가진 수의 개수를 얻을 수 있습니다.
구현 예제
아래 C++ 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int A(int m, int n){
int ret = 1;
for (int i = 0; i < n; i++) {
ret *= m;
m--;
}
return ret;
}
int numDupDigitsAtMostN(int N){
vector<int> arr;
for (int i = N + 1; i > 0; i /= 10) {
arr.insert(arr.begin(), i % 10);
}
int ret = 0;
int n = arr.size();
for (int i = 1; i < n; i++) {
ret += 9 * A(9, i - 1);
}
set<int> visited;
for (int i = 0; i < n; i++) {
int digit = arr[i];
for (int j = i == 0 ? 1 : 0; j < digit; j++) {
if (visited.count(j))
continue;
ret += A(9 - i, n - i - 1);
}
if (visited.count(digit))
break;
visited.insert(digit);
}
return N - ret;
}
};
main(){
Solution ob;
cout << (ob.numDupDigitsAtMostN(99));
}입력
99
출력
9
정리
이 알고리즘은 전체 범위를 일일이 탐색하지 않고 순열 계산만으로 답을 구하므로, N의 자릿수에 비례하는 시간 복잡도(O(log N))로 매우 큰 N도 빠르게 처리할 수 있습니다. 핵심은 '중복 없는 수의 개수'를 구한 뒤 전체 N에서 빼는 역발상이라는 점을 기억하면 됩니다.