C++로 n 이하의 정수 중 중복된 숫자를 가진 수의 개수 구하기

문제 이해하기

정수 n이 하나 주어졌을 때, n 이하의 양의 정수 중에서 적어도 한 개의 자릿수가 두 번 이상 등장하는 수가 몇 개인지 구하는 것이 이 문제의 목표입니다.

예를 들어 입력이 n = 200이라면 출력은 38이 됩니다. 실제로 11, 22, 33처럼 같은 숫자가 반복되는 수나 100, 101처럼 특정 자릿수가 겹치는 수를 1부터 200까지 세어 보면 정확히 38개가 존재합니다.

풀이 전략: 여집합으로 접근하기

중복 자릿수를 가진 수를 직접 세는 것보다, 전체 개수에서 '모든 자릿수가 서로 다른 수'의 개수를 빼는 방식이 훨씬 깔끔하고 효율적입니다.

(중복 자릿수를 가진 수의 개수) = n − (모든 자릿수가 고유한 수의 개수)

구체적인 해결 단계는 다음과 같습니다.

자릿수 분리 — n을 10으로 나눈 나머지를 차례대로 배열 a에 넣은 뒤, 배열을 뒤집어 최상위 자릿수부터 저장합니다.
더 짧은 자릿수의 수 처리 — 자릿수 개수가 n보다 짧은 수들에 대해 곱셈 원리로 '모든 자릿수가 고유한 경우의 수'를 계산해 ret에서 뺍니다. 첫 번째 자리는 1~9 중 하나(9가지), 이후 w번째 자리는 이미 사용한 숫자를 피해야 하므로 min(9, 10 − w + 1)가지를 선택할 수 있습니다.
같은 길이 탐색(go 함수) — n과 자릿수 길이가 같으면서 n 이하인 수들 중 자릿수가 모두 고유한 경우를 비트마스크 b로 추적하며 셉니다. 각 자리에서 현재 자릿값보다 작은 숫자를 놓는 경우의 수를 ret에서 차감하고, 현재 자릿값이 아직 사용되지 않았다면 마스크에 표시한 후 다음 자리로 진행합니다. 이미 사용된 숫자라면 해당 경로는 더 이상 유효하지 않으므로 탐색을 종료합니다.
최종 보정 — n 자체의 자릿수가 모두 고유했다면, 마지막에 ret을 1 줄여 n 본인을 결과에서 제외합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
    vector<int> a;
    for (int x = n; x; x /= 10) a.push_back(x % 10);
    reverse(a.begin(), a.end());
    int ret = n;
    for (int w = 1, d = 1; w < a.size(); ++w) {
        d *= min(9, 10 - w + 1);
        ret -= d;
    }
    auto go = [&]() {
        int b = (1 << 10) - 1;
        for (int i = 0; i < a.size(); ++i) {
            for (int d = (i < 1); d < a[i]; ++d) {
                int x = 0;
                if ((1 << d) & b) ++x;
                for (int j = i + 1; j < a.size(); ++j) x *= 10 - j;
                ret -= x;
            }
            if ((1 << a[i]) & b)
                b ^= (1 << a[i]);
            else
                return;
        }
        --ret;
    };
    go();
    return ret;
}
int main(){
    cout << solve(200) << endl;
    return 0;
}

실행 결과 확인

입력

출력

코드 핵심 정리

이 알고리즘은 n의 자릿수 개수에 비례하는 횟수만 반복하므로 시간 복잡도가 대략 O(log n) 수준입니다. 따라서 n이 매우 커지더라도 빠르게 답을 구할 수 있습니다. 핵심 아이디어는 두 가지로 요약할 수 있습니다.

전체 개수에서 '자릿수가 모두 다른 수'의 개수를 빼는 여집합 계산
비트마스크를 활용해 각 숫자의 사용 여부를 10비트 정수 하나로 관리하는 기법

곱셈 원리로 경우의 수를 누적하는 부분과 비트마스크로 중복 사용을 검사하는 부분을 함께 이해하면, 유사한 자릿수 조합 문제에도 손쉽게 응용할 수 있습니다.