Problem
Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.
Return the number of positive integers that can be generated that are less than or equal to a given integer n.
Example 1:
Input: digits = ["1","3","5","7"], n = 100 Output: 20 Explanation: The 20 numbers that can be written are: 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.Example 2:
Input: digits = ["1","4","9"], n = 1000000000 Output: 29523 Explanation: We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers, 81 four digit numbers, 243 five digit numbers, 729 six digit numbers, 2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers. In total, this is 29523 integers that can be written using the digits array.Example 3:
Input: digits = ["7"], n = 8 Output: 1Constraints:
・ 1 <= digits.length <= 9 ・ digits[i].length == 1 ・ digits[i] is a digit from '1' to '9'. ・ All the values in digits are unique. ・ digits is sorted in non-decreasing order. ・ 1 <= n <= 10⁹
Idea
★ 주의: 코드가 깔끔하지 못 합니다.
Digit 문자열과 숫자 n이 주어진다. Digit으로 된 문자열을 조합하여 n보다 작은 수를 만들 수 있는데, 그 갯수가 몇 개인지 구하는 문제다.
Dynamic Programming을 이용해서 풀 수 있는데, Solution을 보니 수학적 방법으로도 풀 수 있다고 한다.
우선 Dynamic Programming을 이용해서 n의 자릿수바다 작은 수의 개수는 쉽게 구할 수 있다.
dp[i] = dp[1] * dp[i-1]
dp[i]를 i개의 수를 이용해 만들 수 있는 수의 개수라고 하면 위와 같은 공식을 만들 수 있다. 제일 앞 한 자리를 정해놓고 앞에서 구한 한 자리 작은 수의 갯수를 곱하는 것이다.
문제 중 어려운 것은 자릿수가 똑같은 수의 개수를 구하는 것이다. 자릿수가 똑같을 경우 주어진 수 n을 앞에서부터 탐색하여 가짓수를 계산해야 한다.
우선 주어진 수 n의 i번째 자리수가 digits 배열의 몇 번째 index에 있는지 확인한다. digits 배열에 존재할 경우 해당 digit의 index를 리턴하고, 존재하지 않을 경우, 그보다 큰 digit의 index를 사용한다. 이 때 얻은 index를 (현재 자리수-1)번째 dp에 곱해서 가능한 수에 더한다. 예를 들면 주어진 수가 600이고 digits 배열이 ["1","3","5","7"]일 때 600보다 작은 세 자리 수의 개수는 3 * dp[2]인 것으로 확인할 수 있다.
탐색하고 있는 수가 digits 배열에 없다면 탐색을 끝내고 답을 리턴하면 된다. 하지만 계속해서 digits 배열에 있는 수가 나온다면 탐색을 계속해야 한다. 수의 자리수가 작아질 수록 dp의 index도 1씩 감소하며 위와 같은 과정을 지속하면 된다. 만약 마지막 수가 digits 배열에 있다면 가능한 수에 1을 더해준다. 이는 지금까지 n의 i번째 수가 digits 배열에 존재할 경우 i번째 수로 만들 수 있는 가능성을 제외시켰지만, 마지막 자릿수는 가능한 수에 포함되기 때문이다.
위 과정을 모두 끝낸 후 계산한 수를 리턴하면 된다.
Solution
class Solution {
public int atMostNGivenDigitSet(String[] digits, int n) {
int loopCnt = 0;
for (int i=n; i > 0; i /= 10) {
loopCnt++;
}
int[] dp = new int[loopCnt+1];
dp[0] = 1;
dp[1] = digits.length;
for (int i=2; i <= loopCnt; i++) {
dp[i] = dp[1] * dp[i-1];
}
int res = 0;
for (int i=1; i <= loopCnt-1; i++) {
res += dp[i];
}
String number = Integer.toString(n);
for (int i=0; i < number.length(); i++) {
int k = findIndex(digits, number.charAt(i));
res += k * dp[loopCnt-i-1];
if (i == number.length() -1 && contain(digits, number.charAt(i)))
res += 1;
if (!contain(digits, number.charAt(i)))
break;
}
return res;
}
private int findIndex(String[] digits, char c) {
for (int i=0; i < digits.length; i++) {
if (digits[i].charAt(0) >= c)
return i;
}
return digits.length;
}
private boolean contain(String[] digits, char c) {
for (int i=0; i < digits.length; i++) {
if (digits[i].charAt(0) == c)
return true;
}
return false;
}
}Solution을 보니 같은 원리지만 훨씬 간단하게 푼 게 있었다.
class Solution {
public int atMostNGivenDigitSet(String[] D, int N) {
String S = String.valueOf(N);
int K = S.length();
int[] dp = new int[K+1];
dp[K] = 1;
for (int i = K-1; i >= 0; --i) {
// compute dp[i]
int Si = S.charAt(i) - '0';
for (String d: D) {
if (Integer.valueOf(d) < Si)
dp[i] += Math.pow(D.length, K-i-1);
else if (Integer.valueOf(d) == Si)
dp[i] += dp[i+1];
}
}
for (int i = 1; i < K; ++i)
dp[0] += Math.pow(D.length, i);
return dp[0];
}
}같은 자리수에 대해서만 dp로 계산을 하고 다른 자리수는 나중에 따로 더해주는 방식으로 구하는 편이 훨씬 낫다.
Reference
https://leetcode.com/problems/numbers-at-most-n-given-digit-set/
