C++로 특정 범위 내의 모든 '좋은 수(Good Number)' 출력하기

문제 개요

이 문제에서는 세 개의 값 L, R, d가 주어집니다. 우리의 과제는 범위 L부터 R 사이에 있는 수 중에서 좋은 수(good number)이면서 동시에 숫자 d를 자릿수로 포함하지 않는 모든 수를 찾아 출력하는 것입니다.

좋은 수란 각 자릿수가 그보다 오른쪽에 있는(즉, 더 낮은 자리의) 모든 자릿수의 합보다 큰 수를 의미합니다. 예를 들어 732는 좋은 수입니다. 7 > 3+2 이고 3 > 2이기 때문입니다.

예시로 이해하기

입력: L = 400, R = 500, d = 3
출력: 410, 420, 421

설명: 400부터 500 사이의 좋은 수는 410, 420, 421, 430입니다. 하지만 숫자 3을 사용할 수 없으므로 430은 결과에서 제외됩니다.

접근 방법

이 문제를 해결하려면 주어진 범위(L부터 R) 내의 모든 숫자를 하나씩 검사하면 됩니다. 어떤 수가 좋은 수이면서 자릿수 중에 d가 하나도 없다면 출력하고, 그렇지 않으면 건너뜁니다.

좋은 수 판별 방법: 숫자를 오른쪽에서 왼쪽으로 순회하면서 지나온 자릿수의 합계를 유지합니다. 순회하는 어느 시점에서든 현재 자릿수가 누적 합계보다 작거나 같으면 해당 수는 좋은 수가 아니므로 false를 반환합니다.

예제 코드

아래 프로그램을 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인해 보겠습니다.

#include<bits/stdc++.h>
using namespace std;
bool isvalidNumber(int n, int d){
    int digit = n%10;
    int sum = digit;
    if (digit == d)
        return false;
    n /= 10;
    while (n){
        digit = n%10;
        if (digit == d || digit <= sum)
            return false;
        else{
            sum += digit;
            n /= 10;
        }
    }
    return 1;
}
void printGoodNumbersLtoR(int L, int R, int d){
    for (int i=L; i<=R; i++){
        if (isvalidNumber(i, d))
            cout << i << " ";
    }
}
int main(){
    int L = 400, R = 600, d = 3;
    cout<<"All good numbers from "<<L<<" to "<<R<<" that do not contain "<<d<<" are :\n";
    printGoodNumbersLtoR(L, R, d);
    return 0;
}

실행 결과

All good numbers from 400 to 600 that do not contain 3 are −
410 420 421 510 520 521 540

복잡도 분석

범위 내의 각 숫자에 대해 자릿수만큼의 연산(자릿수 개수를 m이라 할 때 O(m))을 수행하므로, 전체 시간 복잡도는 O((R−L+1) × m)입니다. 추가적인 공간은 상수 크기만 사용되므로 공간 복잡도는 O(1)입니다.