[Leetcode] 902. Numbers At Most N Given Digit Set

문제 : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/

---

내림차순으로 정렬된 숫자 배열 digits와 정수 n이 주어진다.

digits 배열의 숫자는 원하는 만큼 재사용 가능하다.

digits 수들을 이용하여 숫자를 만들 때, 정수 n보다 작거나 같은 정수들의 갯수를 구하라.

---

예시를 직접 풀면서 알아보자.

digits = ["1", "3", "5"], n = "355"

입력 값이 위와 같을 때, 일의 자리(x), 십의 자리(xx) 수들은 모두 정답에 포함된다.

따라서 이들 개수는 정답에 미리 더해둔다.

x 에 digits 들 중 어느 숫자가 와도 상관없으므로 조합을 생각하면 각 자리에 3개의 수가 올 수 있으므로 일의 자리의 경우의 수는 3, 십의 자리의 경우의 수는 3 x 3 = 9 이다.

 

이제 백의 자리로 만들 수 있는 수 있는 수들 중 n 보다 작을 경우의 수를 구해야 한다.

이 때도 위와 같은 방법으로 개수를 구할 수 있다.

 

백의 자리 부터 digits을 채워나가보자.

1. 1xx : 백의 자리가 n보다 작으므로 이후에 어떤 수가 와도 정답이 가능하다. 따라서, 3 x 3 = 9를 정답에 더해준다.

2. 3xx : 백의 자리가 n과 같으므로 이후에 나오는 수들을 봐야 한다.

3. 5xx : 백의 자리가 n보다 크므로 이후에 어떤 수가 와도 정답이 불가능하다.

백의 자리만 봤을 때, 백의 자리가 n 보다 작은 1번의 경우는 모두 정답에 더해주었고 3번은 정답이 불가능하다. 이제 십의 자리를 탐색할 텐데 위의 경우에서 아직 정답이 될 가능성이 있는 경우는 2번 밖에 없다. 따라서 백의 자리는 3으로 고정하고 탐색을 이어나간다. 만일 정답이 될 가능성이 없는 경우(2번과 같은 경우가 존재하지 않는 경우)는 탐색을 종료한다.

 

십의 자리의 digits을 채워나가보자. 백의 자리는 동일하므로 백의 자리와 동일하게 비교한다.

1. 31x : 십의 자리가 n보다 작으므로 이후에 어떤 수가 와도 정답이 가능하다. 따라서, 3을 정답에 더해준다.

2. 33x : 십의 자리가 n보다 작으므로 이후에 어떤 수가 와도 정답이 가능하다. 따라서, 3을 정답에 더해준다.

3. 35x : 십의 자리가 n과 같으므로 이후에 나오는 수들을 봐야 한다.

마찬가지로 아직 정답이 될 가능성이 남은 3번을 마저 탐색하기 위해 십의 자리를 5로 고정한 채 1의 자리를 탐색한다.

 

일의 자리의 digits을 채워보자.

1. 351 : 일의 자리가 n보다 작으므로 정답이 가능하다. 따라서, 1을 정답에 더해준다.

2. 353 : 일의 자리가 n보다 작으므로 정답이 가능하다. 따라서, 1을 정답에 더해준다.

3. 355 : 일의 자리가 n과 같으므로 이후에 나오는 수들을 봐야한다.

3번 같은 경우 이후에 나오는 수들을 봐야하지만 모든 자리 수를 탐색했으므로 3번의 경우도 정답이 가능하다. 따라서, 마찬가지로 1을 정답에 더해준다.

 

따라서 위 예시의 경우, 12 + 9 + 6 + 3 = 30 이 정답이 된다.

 

시간복잡도는 O(NM). N = |n|, M = |digits|.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/902.%20Numbers%20At%20Most%20N%20Given%20Digit%20Set.cpp