범위 내 특정 자릿수의 등장 횟수 효율적으로 계산하기

문제 소개

0부터 9 사이의 정수 하나(d)와 두 개의 양의 정수 low, high가 주어집니다. 이때 low부터 high까지(양 끝값 포함)의 모든 정수에서 숫자 d가 총 몇 번 등장하는지 구해야 합니다.

예를 들어 d = 1, low = 1, high = 13이 입력으로 주어지면 결과는 6입니다. 1, 10, 11, 12, 13 안에서 숫자 1이 총 6번 나타나기 때문입니다.

해결 전략

구간의 모든 수를 하나씩 직접 확인하는 방법도 있지만, 자릿수의 규칙성을 활용하면 훨씬 빠르게 계산할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

f(x, n) : 1부터 n까지의 모든 정수에서 숫자 x가 등장하는 횟수를 반환하는 함수를 정의합니다.
그러면 [low, high] 구간에서의 등장 횟수는 f(d, high) − f(d, low − 1)로 간단히 구할 수 있습니다.

특히 숫자 0은 선행 자릿수(leading zero)가 없다는 점에서 다른 숫자와 계산 방식이 달라지므로, 이를 처리하기 위한 별도의 zero() 로직이 필요합니다.

알고리즘 단계

f(x, n) 함수

ret := 0으로 초기화합니다.
m을 1부터 시작해 m ≤ n인 동안 m을 10배씩 늘려가며 반복합니다.
a := n / m (현재 자리보다 높은 부분), b := n mod m (현재 자리보다 낮은 부분), z := a mod 10 (현재 자리의 숫자)
z > x이면 : ret := ret + ((a / 10) + 1) × m
z == x이면 : ret := ret + ((a / 10) × m + (b + 1))
z < x이면 : ret := ret + (a / 10) × m
x == 0이면 선행 0을 제외하기 위해 ret := ret − m

반복이 끝나면 ret을 반환합니다.

zero(n) 함수

n이 0이면 1을 즉시 반환합니다.
그 외에는 위와 유사한 방식으로 각 자리별 0의 개수를 누적하되, m의 자릿수가 n의 자릿수와 같아지면 반복을 종료합니다.

메인 로직

최종 답은 f(d, high) − f(d, low − 1) 입니다. 이 방식의 시간 복잡도는 자릿수에 비례하는 O(log₁₀ n)으로 매우 효율적입니다.

C++ 구현 예시

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int digitCount(int x){
        int ret = 0;
        while (x) {
            ret++;
            x /= 10;
        }
        return ret;
    }
    int zero(int n){
        int ret = 0;
        int x = 0;
        if (n == 0)
        return 1;
        for (int m = 1; m <= n; m *= 10) {
            int a = n / m;
            int b = n % m;
            int z = a % 10;
            if (digitCount(m) == digitCount(n))
            break;
            if (z > x) {
                ret += ((a / 10) + 1) * m;
            } 
            else if (z == x) {
                ret += (a / 10) * m + (b + 1);
            } else {
                ret += (a / 10) * m;
            }
            cout << ret << endl;
        }
        return ret;
    }
    int f(int x, int n){
        int ret = 0;
        for (int m = 1; m <= n; m *= 10) {
            int a = n / m;
            int b = n % m;
            int z = a % 10;
            if (z > x) {
                ret += ((a / 10) + 1) * m;
            }
            else if (z == x) {
                ret += (a / 10) * m + (b + 1);
            } else {
                ret += (a / 10) * m;
            }
            if (x == 0) {
                ret -= m;
            }
        }
        return ret;
    }
    int digitsCount(int d, int low, int high){
        return f(d, high) - f(d, low - 1);
    }
};
main(){
    Solution ob;
    cout << (ob.digitsCount(1,1,13));
}

입력

1, 1, 13