C++로 1부터 n까지의 숫자 중 자릿수에 4가 포함된 개수 구하기

이 튜토리얼에서는 1부터 n까지의 숫자 중에서 자릿수에 4가 포함된 숫자의 개수를 구하는 프로그램을 다룹니다.

하나의 숫자 n이 주어지면, 우리의 목표는 그 범위 안에서 4를 자릿수 중 하나로 가지는 모든 숫자를 세어 그 결과를 출력하는 것입니다.

예를 들어 n이 328이라면, 4, 14, 24, 34, 40~49 등처럼 어느 자리든 4가 들어간 숫자들을 모두 찾아 합산해야 합니다.

구현 예제

#include<iostream>
using namespace std;
bool has4(int x);
// 주어진 범위에서 조건을 만족하는 숫자의 개수 반환
int get_4(int n){
    int result = 0;
    // 각 숫자마다 4의 포함 여부를 확인하여 합산
    for (int x=1; x<=n; x++)
        result += has4(x)? 1 : 0;
    return result;
}
// 해당 숫자의 자릿수에 4가 있는지 검사
bool has4(int x) {
    while (x != 0) {
        if (x%10 == 4)
            return true;
        x = x /10;
    }
    return false;
}
int main(){
    int n = 328;
    cout << "Count of numbers from 1 to " << n
        << " that have 4 as a digit is "
        << get_4(n) << endl;
    return 0;
}

동작 원리

핵심 로직은 두 함수로 나뉩니다. 먼저 has4() 함수는 전달받은 숫자를 10으로 나눈 나머지(x % 10)를 이용해 일의 자리부터 차례대로 검사합니다. 각 자릿수가 4와 같으면 즉시 true를 반환하고, 모든 자릿수를 확인할 때까지 10으로 나누며 자릿수를 하나씩 제거합니다.

그다음 get_4() 함수는 1부터 n까지 모든 숫자를 반복하면서 has4()의 결과가 참일 때마다 카운트를 1씩 증가시켜 최종 개수를 반환합니다.

출력 결과

Count of numbers from 1 to 328 that have 4 as a digit is 60

위 코드를 실행하면 1부터 328 사이에서 자릿수에 4가 포함된 숫자는 총 60개임을 확인할 수 있습니다.

시간 복잡도

이 방식은 각 숫자의 자릿수만큼 연산을 수행하므로, 전체 시간 복잡도는 O(n × d)입니다. 여기서 d는 숫자의 평균 자릿수입니다. n이 매우 큰 경우에는 자릿수 조합을 활용한 수학적 접근으로 더 빠르게 계산할 수 있습니다.