LeetCode : 357. Count Numbers with Unique Digits

 

문제)

주어진 정수 n에 대해 0부터 10^n 미만의 모든 수 중에서 각 자리의 숫자가 고유한 숫자의 개수를 반환해야함.

즉, 중복된 숫자를 가지지 않는 수의 개수를 계산하는 것.

 

 

소요시간 및 풀이)

역시 수학적 머리를 써야하는 문제는 어김없이 못 푸는것 같다.

머리를 써봤지만 식을 세우지 못해 코드조차 치지 못하였다.

식만 알면 코드는 매우 간단하다.

 

n=3일 경우

1. 0부터 10^n 미만의 모든 수 중에서 각 자리의 숫자가 고유한 숫자인 경우를 찾아야 함.

2. 첫 번째 자리에는 0을 포함할 수 없으며, 1~9까지의 숫자 중에서 선택 가능.

3.두 번째 자리부터는 0~9까지의 숫자 중에서 선택 가능.

하지만 첫 번째 자리에서 선택한 숫자는 두 번째 자리에서 다시 선택할 수 없으므로 0~9의 숫자중에서 선택 가능한 경우는 9가지이다.

4.세 번째 자리부터는 0~9의 숫자 중에서 선택 가능. 하지만 첫 번째와 두 번째 자리에서 선택한 숫자는 선택 불가능하므로 선택 가능한 경우는 8가지이다.

5.이와 같은 방식으로 계속하여 10^n 미만의 모든 수 중에서 각 자리의 숫자가 고유한 숫자인 경우를 계산 해야함.

 

• countNumbersWithUniqueDigits(int n) 함수는 'n'자리 숫자의 개수를 반환.
  재귀적으로 호출하여 모든 자릿수에 대한 숫자의 개수를 계산.
  
  9*fac(9)로 모든 경우의 수 계산.
  계산한 값을 fac(10-n)으로 나눠서 첫 번째 자리에서 선택한 숫자를 제외하고 남은 선택할 수 있는 숫자의 개수.
  이 과정을 재귀적으로 진행.
  
  
• fac(int n)
  팩토리얼 값을 계산.

 

문제 난이도 : 중

 

 

정답 코드

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) 
    {
        return n > 0 ? 9 * fac(9) / fac(10 - n)
            + countNumbersWithUniqueDigits(n - 1) : 1;
    }

    int fac(int n) 
    {
        return n > 1 ? n * fac(n - 1) : 1;
    }
};