Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 특정 숫자를 포함하지 않는 n자리 수의 개수 구하기

문제 정의

정수 digit(제외할 숫자)와 자릿수 n이 주어졌을 때, 그 숫자를 단 한 번도 포함하지 않는 n자리 자연수가 총 몇 개 존재하는지 계산하는 것이 이 글의 목표입니다.

입력 − n = 2, digit = 2
출력 − 72
설명 − 두 자리 수(10~99) 중 숫자 2가 들어 있지 않은 수는 10, 11, 13, 14, 15, 16, 17, 18, 19, 30, 31, 33, 34, … 등입니다. 십의 자리에 올 수 있는 숫자는 1~9 중 2를 제외한 8가지, 일의 자리는 0~9 중 2를 제외한 9가지이므로 총 8 × 9 = 72개입니다.

입력 − n = 3, digit = 3
출력 − 648
설명 − 세 자리 수(100~999) 중 숫자 3이 들어 있지 않은 수는 백의 자리 8가지 × 십의 자리 9가지 × 일의 자리 9가지 = 648개입니다.

완전 탐색(Brute Force) 접근 방식

  • n과 digit을 정수 변수로 입력받아, 개수를 계산하는 함수에 전달합니다.
  • n자리 수의 범위를 먼저 결정합니다. 최솟값(min)은 10n-1, 최댓값(max)은 10n입니다. 예를 들어 두 자리 수는 10~99, 세 자리 수는 100~999 범위를 가집니다.
  • min부터 max 미만까지 반복문을 실행합니다.
  • 반복문 안에서 각 수의 자릿수를 하나씩 분리하며(10으로 나눈 나머지와 몫을 활용) 주어진 digit이 포함되어 있는지 검사합니다.
  • digit이 발견되면 해당 수는 건너뛰고, 끝까지 발견되지 않으면 카운트를 1 증가시킵니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 특정 숫자를 포함하지 않는 n자리 수의 개수를 세는 함수
int countNumbers(int n, int digit) {
    // n자리 수의 최솟값과 최댓값 계산
    int min = (int)pow(10, n - 1);
    int max = (int)pow(10, n);

    int cnt = 0;
    // min부터 max 미만까지 모든 수 검사
    for (int i = min; i < max; i++) {
        int a = i;
        bool found = false;
        // 각 자릿수를 분리하며 digit 검사
        while (a > 0) {
            int r = a % 10;
            a /= 10;
            if (r == digit) {
                found = true;
                break;
            }
        }
        // digit이 없으면 카운트 증가
        if (!found) {
            cnt++;
        }
    }
    return cnt;
}

int main() {
    int n = 2, digit = 2;
    cout << "숫자 " << digit << " 없이 만들 수 있는 " << n
         << "자리 수의 개수 : " << countNumbers(n, digit);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻습니다.

숫자 2 없이 만들 수 있는 2자리 수의 개수 : 72

더 효율적인 방법: 곱셈 원리 활용

위 완전 탐색 방식은 시간 복잡도가 대략 O(n × 10n)으로, n이 커지면 실행 속도가 급격히 느려집니다. 사실 이 문제는 자릿수별 선택지를 곱하는 간단한 조합 원리로 O(n) 만에 해결할 수 있습니다.

  • 최상위 자리에는 0이 올 수 없으므로 후보는 1~9입니다. 여기서 digit을 제외하면 digit ≠ 0일 때 8가지, digit = 0일 때 9가지입니다.
  • 나머지 자리마다 0~9 중 digit 하나만 제외하면 되므로 각 자리마다 9가지씩 선택 가능합니다.
  • 따라서 답은 digit ≠ 0일 때 8 × 9n-1, digit = 0일 때 9 × 9n-1 = 9n입니다.
#include <bits/stdc++.h>
using namespace std;

// 곱셈 원리로 O(n)에 답을 구하는 함수
long long countFast(int n, int digit) {
    // 첫 자리: 0은 불가능하고 digit은 제외
    long long result = (digit == 0) ? 9 : 8;
    // 나머지 자리: digit 하나만 제외하므로 매번 9가지
    for (int i = 1; i < n; i++) {
        result *= 9;
    }
    return result;
}

int main() {
    int n = 3, digit = 3;
    cout << "숫자 " << digit << " 없이 만들 수 있는 " << n
         << "자리 수의 개수 : " << countFast(n, digit);
    return 0;
}

실행 결과:

숫자 3 없이 만들 수 있는 3자리 수의 개수 : 648

마무리

범위 전체를 직접 순회하는 완전 탐색은 로직이 직관적이라 이해하기 쉽지만, n이 커지면 비효율적입니다. 자릿수별 선택지를 곱하는 조합적 사고를 적용하면 동일한 답을 훨씬 빠르게 얻을 수 있으므로, 실제 코딩 테스트에서는 공식 기반 풀이를 사용하는 것이 좋습니다.