Count Numbers With Unique Digits
1. 개요
이 문서에서는 주어진 정수를 초과하지 않는 고유한 자릿수를 가진 숫자의 개수를 세는 문제를 탐구합니다.
무차별 대입부터 최적화된 방법까지 효율적인 솔루션을 살펴보며, 시간과 공간 복잡도에 대한 예제와 분석을 제공합니다.
2. 문제 설명
정수 n이 주어졌을 때, 다음 조건을 만족하는 고유한 자릿수를 가진 모든 양의 숫자 x의 개수를 세야 합니다:
- 0 <= x < 10n
즉, x는 10n 미만의 양의 정수입니다.
- x의 각 자릿수는 중복되지 않아야 합니다.
여기 몇 가지 예시가 있습니다:
- n = 0일 경우 조건을 충족하는 유일한 숫자는 0입니다.
- n = 1일 경우 자릿수가 한 개인 모든 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10입니다.
- n = 2일 경우 자릿수가 두 개인 모든 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13 등입니다. (11은 포함되지 않음을 주의하세요.)
- n = 3일 경우 고유한 자릿수를 가진 숫자로는 0, 1, 2, 3, 12, 13, 23, 345, 745 등이 포함됩니다.
- n = 4일 경우 고유한 자릿수를 가진 숫자로는 0, 1, 2, 3, 12, 13, 23, 345, 745, 1234, 1567 등이 포함됩니다.
3. 솔루션
3.1. 무차별 대입 방법
무차별 대입 방법은 모든 숫자를 생성하고 각 숫자가 고유한 자릿수를 가지고 있는지를 확인하는 직관적인 접근 방식입니다. 그러나 n이 증가함에 따라 계산 비용이 많이 듭니다.
무차별 대입 방법에서는 10n 미만의 모든 숫자를 반복합니다. 각 숫자에 대해 자릿수가 고유한지 확인하고 이 조건을 충족하는 숫자의 개수를 센다:
int bruteForce(int n) {
int count = 0;
int limit = (int) Math.pow(10, n);
for (int num = 0; num < limit; num++) {
if (hasUniqueDigits(num)) {
count++;
}
}
return count;
}
hasUniqueDigits 함수는 주어진 숫자가 반복되는 자릿수가 없는지 확인하기 위해 문자열로 변환하고 각 자릿수를 서로 비교합니다. 중복 자릿수가 발견되면 false를 반환하고, 그렇지 않으면 true를 반환합니다:
boolean hasUniqueDigits(int num) {
String str = Integer.toString(num);
for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j < str.length(); j++) {
if (str.charAt(i) == str.charAt(j)) {
return false;
}
}
}
return true;
}
다음 테스트를 수행하여 이 알고리즘을 검증합시다:
@Test
void givenNumber_whenUsingBruteForce_thenCountNumbersWithUniqueDigits() {
assertEquals(91, UniqueDigitCounter.bruteForce(2));
}
시간 복잡도는 O(10n)이며, n은 가장 큰 숫자의 자릿수입니다. 각 숫자의 자릿수의 고유성을 확인하기 때문입니다. 공간 복잡도는 각 숫자의 문자열 표현으로 인해 O(n)입니다.
3.2. 조합론적 접근
처리를 최적화하기 위해 조합론적 접근을 적용할 수 있습니다. 무차별 대입을 사용하기보다, 각 자릿수 위치를 개별적으로 고려하고 순열을 활용하여 유효한 숫자의 개수를 계산합니다.
이 방법은 무차별 대입보다 훨씬 효율적입니다. 각 자릿수에 대해 일정한 작업만 필요하여 큰 n의 값에 대해서도 실행이 가능합니다.
다음과 같은 관찰을 살펴보겠습니다:
- n = 0일 경우, 유일한 유효 숫자는 0이므로 1을 반환합니다.
- n = 1일 경우, 자릿수는 0에서 9까지 가능하여 총 10개의 가능한 숫자가 생성됩니다.
- n > 1일 경우:
- 첫 번째 자릿수는 1부터 9까지의 9개의 선택지가 있습니다. (0은 첫 자릿수가 될 수 없기 때문입니다.)
- 두 번째 자릿수는 첫 번째 자릿수를 제외한 0부터 9까지의 9개의 선택지가 있습니다.
- 세 번째 자릿수는 8개의 선택지가 있으며, 이와 같이 계속됩니다.
k자릿수 숫자의 경우, 유효한 숫자의 수는 순열을 사용하여 계산할 수 있습니다:
int combinatorial(int n) {
if (n == 0) return 1;
int result = 10;
int current = 9;
int available = 9;
for (int i = 2; i <= n; i++) {
current *= available;
result += current;
available--;
}
return result;
}
위 접근 방식이 올바르게 작동하는지 테스트해보겠습니다:
@Test
void givenNumber_whenUsingCombinatorial_thenCountNumbersWithUniqueDigits() {
assertEquals(91, UniqueDigitCounter.combinatorial(2));
}
시간 복잡도는 O(n)이며 각 자릿수를 한 번 처리하므로 공간 복잡도는 O(1)입니다. 몇 개의 변수만 사용하기 때문입니다.
4. 결론
이 문서에서는 고유한 자릿수를 가진 숫자를 세는 두 가지 접근 방식을 탐구했습니다. 무차별 대입 접근법은 모든 숫자를 확인하므로 큰 n에 대해 비효율적이며, 조합론적 접근은 효율적인 O(n) 솔루션을 위해 순열을 사용합니다.
이 문서의 코드 구현은 GitHub에서 확인할 수 있습니다. 로그인한 후 Baeldung Pro 회원으로 프로젝트에서 학습하고 코딩을 시작하세요.
쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
