C++로 특수 숫자(Special Number)의 총 자릿수 구하기

문제 설명

정수 k가 주어집니다. 모든 자릿수가 동일한 숫자를 특수 숫자(special number)라고 부릅니다. 예를 들어 1, 11, 1111은 모두 특수 숫자입니다. 특수 숫자는 1, 11, 111, 1111, 2, 22, 222, 2222, 3, 33, 333, 3333, ... 과 같은 순서로 나열됩니다. 우리가 구해야 할 값은 k까지 등장하는 특수 숫자들이 가진 자릿수의 총합입니다. 단, k의 값은 10000을 넘지 않습니다.

예를 들어 입력이 k = 9999라면 출력은 90이 됩니다.

접근 방법

이 문제는 반복문 없이 수학적 규칙만으로 O(1) 시간에 해결할 수 있습니다. 풀이 절차는 다음과 같습니다.

s := k를 문자열로 변환
배열 v := {0, 1, 3, 6, 10} 정의
출력: ((s[0] - '0') - 1) * 10 + v[s의 길이]

여기서 배열 v는 1부터 n까지의 합(1+2+...+n)을 미리 계산해 둔 누적합 배열입니다. 즉, v[i]는 i자리 특수 숫자 하나가 기여하는 자릿수의 누적값을 의미합니다.

공식의 원리를 살펴보면 다음과 같습니다.

• k보다 앞순서인, 첫 자릿수가 더 작은 숫자들(d, dd, ddd, dddd)은 각 시작 숫자마다 4개씩 존재하며, 자릿수의 합은 1+2+3+4 = 10입니다. 따라서 (첫 자릿수 - 1) × 10을 더해 줍니다.
• 첫 자릿수가 k와 같은 경우에는, k의 길이까지만 특수 숫자를 세면 되므로 누적합 v[s의 길이]를 더해 줍니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int k) {
    string s = to_string(k);
    int v[] = {0, 1, 3, 6, 10};
    cout << ((s[0] - '0') - 1) * 10 + v[s.length()] << endl;
}
int main() {
    int k = 9999;
    solve(k);
    return 0;
}

입력

9999

출력

90

복잡도 분석

이 풀이는 문자열 변환 한 번과 상수 개수의 연산만 수행하므로, 시간 복잡도와 공간 복잡도가 모두 O(1)입니다. k의 최댓값이 10000으로 제한되어 있기 때문에 누적합 배열 v의 크기도 5로 충분합니다.