Count Numbers With Unique Digits

1. 개요

이 글에서는 고유한 숫자를 가진 숫자를 센다는 문제를 다루며, 숫자의 총 자릿수가 주어진 정수를 초과하지 않는 조건을 탐구합니다.

우리는 비효율적인 방법에서 최적화된 방법까지 효율적인 솔루션을 살펴보며, 시간 및 공간 복잡성에 대한 예제와 분석도 함께할 것입니다.

2. 문제 진술

정수 n이 주어지면, 다음 조건을 만족하는 고유한 숫자를 가진 모든 양의 숫자 x를 세야 합니다:

• 0 <= x < 10ⁿ

즉, x는 10ⁿ보다 작은 양의 정수입니다.

• 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이라면, 1000보다 작은 고유한 자리를 가진 숫자는 0, 1, 2, 3, 12, 13, 23, 345, 745, 등입니다.
• 만약 n = 4라면, 10000보다 작은 고유한 자리를 가진 숫자는 0, 1, 2, 3, 12, 13, 23, 345, 745, 1234, 1567, 등입니다.

3. 해결책

3.1. 무차별 대입 접근법

직관적인 접근법은 무차별 대입 방법으로, 10ⁿ보다 작은 모든 숫자를 생성하고 각 숫자가 고유한 자리수를 가지는지 확인하는 방법입니다. 그러나, n이 커질수록 계산 비용이 많이 발생합니다.

무차별 대입 방법에서, 우리는 10ⁿ보다 작은 모든 숫자에 대해 반복합니다. 각 숫자에 대해 자리가 고유한지 확인하고, 조건을 만족하는 숫자의 개수를 셉니다:

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(10ⁿ)이며, n은 가장 큰 숫자의 자리 수입니다. 각 숫자의 자리를 고유성으로 체크하기 때문입니다. 공간 복잡도는 각 숫자의 문자열 표현을 사용하여 O(n)입니다.

3.2. 조합 접근법

프로세스를 최적화하기 위해 조합 접근법을 적용할 수 있습니다. 무차별 대입을 사용하는 대신, 각 숫자 위치를 개별적으로 고려하고 순열을 활용하여 유효한 숫자의 수를 계산합니다.

이 접근법은 무차별 대입보다 훨씬 효율적이며, 각 자리에 대해 일정한 작업만 필요하므로 더 큰 값의 n에 대해 실행 가능하게 합니다.

다음과 같은 관찰을 해보겠습니다:

• n = 0일 때, 유일한 유효 숫자는 0이므로 1을 반환합니다.
• n = 1일 때, 자리는 0부터 9까지 가능하므로 10개의 가능한 숫자가 있습니다.
• n > 1일 때: 첫 번째 자리는 9개의 선택지 (1부터 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보다 작은 고유한 숫자를 세는 두 가지 접근법을 탐구했습니다. 무차별 대입 접근법은 모든 숫자를 검사하며 n이 커질수록 비효율적입니다. 반면, 조합 접근법은 효율적인 O(n) 솔루션을 제공합니다.

전체 소스 코드는 GitHub에서 확인하실 수 있습니다.

원본 출처