https://www.acmicpc.net/problem/1019

---

문제

---

첫 시도

0부터 9, 10부터 99, 100부터 999···
이런 식으로 각각의 개수를 구해서 규칙을 찾아 그 수를 뺀 후, 나머지는 일일이 계산하려고 했다.

그런데 N의 범위는 1,000,000,000보다 작거나 같은 자연수이므로 999,999,998와 같은 숫자가 입력되었을 때 899,999,999번 계산해야 하므로 시간복잡도가 높아질 것 같아서 다른 방법을 찾아봤다.

---

풀이

일의 자리 숫자 계산

십의 자리 숫자 계산

백의 자리 숫자 계산

정리

n의 i의 자리 숫자가 x라고 가정했을 때

i의 자리 숫자 < x : (n // (i × 10) + 1) × i번
i의 자리 숫자 == x : (n // (i × 10)) + (n % i) + 1번
i의 자리 > x : n // (i × 10)번
ㄴ 0의 보정으로 0은 추가로 i 값만큼 빼준다

---

코드

수식을 그대로 대입하면 이렇게 된다.

cnt = [0] * 10  # 0 ~ 9의 각 등장 횟수
i = 1  # 자릿수 계산

n = int(input())

while i <= n: # 계산해야 하는 자릿수가 n보다 커지면 종료
    x = n % (i*10) // i # i의 자리 숫자

    # x보다 작은 숫자 계산
    for j in range(x): cnt[j] += (n // (i*10) + 1) * i

    # x 계산
    cnt[x] += (n // (i*10))*i + (n%i) + 1

    # x보다 큰 숫자 계산
    for j in range(x + 1, 10): cnt[j] += (n // (i * 10)) * i

    cnt[0] -= i # 0의 보정
    i *= 10 # 자릿수 올리기


print(*cnt)

간단하게 이렇게 정리할 수 있다.

cnt = [0] * 10
i = 1 # 자릿수
add = 0 # n % i 값

n = int(input())

while n: # n이 0이 아닌동안
    x = n%10 # i의 자릿수 숫자
    n//=10 # n에서 제일 뒷자리수 제거
    
    # x보다 작은 숫자 계산
    for j in range(x): cnt[j] += (n+1)*i
    
    # x 계산
    cnt[x] += n*i + add+1
    
    # x보다 큰 숫자 계산
    for j in range(x+1, 10): cnt[j] += n*i
        
    add += x*i # n%i값 수정
    cnt[0] -= i # 0의 보정
    i*=10
print(*cnt)

---

참고
https://restudycafe.tistory.com/489