C++로 풀어보는 주어진 자릿수 집합으로 만들 수 있는 N 이하의 숫자 개수

문제 개요

정렬된 자릿수 집합 D가 주어집니다. D는 0을 제외한 {1, 2, 3, 4, 5, 6, 7, 8, 9}의 공집합이 아닌 부분집합입니다. 우리는 이 자릿수들을 사용해 각 숫자를 원하는 만큼 반복하여 여러 수를 만들 수 있습니다. 예를 들어 D = {'2', '3', '7'}이라면 '23', '771', '2372327'과 같은 수를 작성할 수 있습니다.

이 문제의 목표는 위 방식으로 만들 수 있는 양의 정수 중 N 이하인 수의 개수를 구하는 것입니다.

예를 들어 입력이 D = [2, 3, 4, 7], N = 100이라면 출력은 20이 됩니다. 만들 수 있는 수는 2, 3, 4, 7, 22, 23, 24, 27, 32, 33, 34, 37, 42, 43, 44, 47, 72, 73, 74, 77이며, 그 외의 모든 조합은 100보다 크기 때문입니다.

해결 알고리즘

이 문제는 다음 단계를 따라 해결할 수 있습니다.

N을 문자열 n으로 변환합니다.
n의 길이를 sz로, 결과값 ret은 0으로 초기화합니다.
i가 1부터 sz 미만일 때까지 반복하면서 ret에 (D의 크기)^i를 더합니다. 이는 i자리 숫자를 만들 수 있는 모든 경우의 수를 누적하는 과정입니다.
다시 i가 0부터 sz 미만까지 반복하면서 각 자릿수를 앞에서부터 비교합니다.
- hasSameNum을 false로 초기화합니다.
- D의 각 숫자 x에 대해 x[0]이 n[i]보다 작다면, 해당 자릿수에 x를 배치하고 나머지 뒷자리를 자유롭게 채우는 경우의 수인 (D의 크기)^(sz - i - 1)을 ret에 더합니다.
- x[0]이 n[i]와 같다면 hasSameNum을 true로 설정합니다.
자릿수 탐색 후 hasSameNum이 false라면 더 이상 유효한 조합을 만들 수 없으므로 즉시 ret을 반환합니다.
모든 자릿수가 N과 일치하여 끝까지 진행되었다면 N 자신도 포함되므로 ret + 1을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int atMostNGivenDigitSet(vector<string> &D, int N) {
        string n = to_string(N);
        int sz = n.size();
        int ret = 0;
        for (int i = 1; i < sz; i++) {
            ret += pow(D.size(), i);
        }
        for (int i = 0; i < sz; i++) {
            bool hasSameNum = false;
            for (string &x : D) {
                if (x[0] < n[i]) {
                    ret += pow(D.size(), sz - i - 1);
                } else if (x[0] == n[i]) {
                    hasSameNum = true;
                }
            }
            if (!hasSameNum)
            return ret;
        }
        return ret + 1;
    }
};
main(){
    Solution ob;
    vector<string> v = {"2","3","4","7"};
    cout << (ob.atMostNGivenDigitSet(v, 100));
}

입력

{"2","3","4","7"}, 100