C++로 n 이하의 모든 숫자에서 1의 개수 구하기

문제 개요

숫자 n이 주어졌을 때, 0부터 n까지의 모든 음이 아닌 정수 안에서 숫자 1이 등장하는 총 횟수를 구하는 문제입니다. 예를 들어 입력이 15라면 출력은 8이 됩니다. 1이 포함된 숫자들은 [1, 10, 11, 12, 13, 14, 15]이며, 이 안에는 1이 총 8번 나타나기 때문입니다.

접근 방법

모든 숫자를 하나씩 확인하는 방법도 있지만, 입력이 커지면 매우 비효율적입니다. 대신 각 자릿수(일의 자리, 십의 자리, 백의 자리 등)별로 1이 몇 번 등장하는지 계산한 뒤 모두 더하면, n의 자릿수에 비례하는 시간 안에 빠르게 해결할 수 있습니다.

n을 현재 자릿수 기준으로 세 부분으로 나누어 생각합니다.

a := n / i — 현재 자릿수를 포함한 윗부분
b := n mod i — 현재 자릿수보다 아래쪽의 나머지 부분
x := a mod 10 — 현재 자릿수의 숫자

현재 자릿수 값 x에 따라 1의 개수를 다음과 같이 누적합니다.

x가 1인 경우: ret = ret + (a / 10) * i + (b + 1)
x가 0인 경우: ret = ret + (a / 10) * i
x가 2~9인 경우: ret = ret + (a / 10 + 1) * i

알고리즘 단계

결괏값 ret을 0으로 초기화합니다.
i := 1부터 시작하여 i <= n인 동안 i를 10배씩 늘려가며 반복합니다.
각 반복마다 a := n / i, b := n mod i, x := a mod 10을 계산합니다.
x의 값이 1, 0, 그 외인지에 따라 위 규칙대로 ret에 더합니다.
반복이 끝나면 ret을 반환합니다.

C++ 구현 예제

다음 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int countDigitOne(int n) {
        int ret = 0;
        for(long long int i = 1; i <= n; i*= (long long int)10){
            int a = n / i;
            int b = n % i;
            int x = a % 10;
            if(x ==1){
                ret += (a / 10) * i + (b + 1);
            }
            else if(x == 0){
                ret += (a / 10) * i;
            } else {
                ret += (a / 10 + 1) *i;
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.countDigitOne(15));
}

입력

출력

복잡도 분석

시간 복잡도는 n의 자릿수에 비례하므로 O(log n)이며, 추가적인 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.