[알고리즘 문제] 자릿수 세기 (Python / 파이썬)

문제

유니는 오늘 1억이라는 큰 수를 배웠다. 이제 유니는 1부터 1억까지의 자연수를 모두 적을 수 있다.
끈기가 대단한 유니는 종이에 1부터 1억까지 수를 순서대로 이어서 적고 있다. 그런데 N까지 적은 순간 문득 지금까지 몇 개의 숫자를 적었는지 궁금해졌다.
유니가 몇 개의 숫자를 적었는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N이 주어진다
( 1 ≤ T ≤ 10, 1 ≤ N ≤ 100,000,000 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 유니가 적은 숫자의 개수를 출력한다.

---

문제 풀이

자릿수 세기 문제는 유니가 n까지 수를 적었을 때 총 몇개의 수를 적었는지 구하는 문제 입니다.

처음엔 유니가 적은 수들을 문자열로 여겨 길이를 더하는 방식을 이용했으나 

시간 초과 문제가 발생했습니다. 따라서 문제를 수학적으로 접근해 해결해보았습니다. 

 

n이 1~9 안에 포함되었을 때 수의 개수 -> 1 * (n - 1 + 1) 

n이 10~99 안에 포함되었을 때 수의 개수 -> 2 * (n - 10 + 1) + 9

n이 100~999 안에 포함되었을 때 수의 개수 -> 3 * (n - 100 + 1) + 9 + 2 * 90

 

n까지 수들의 총 개수는 위의 식을 만족합니다. 따라서 위의 식대로 문제를 해결해주었습니다.

예를 들어, n이 156이라면 100~156 까지 총 3 * (156 - 100 + 1) 개가 존재하며

1~99까지 9 + 2 * 90 개의 수가 존재합니다. 이를 모두 더해주면 총 수의 개수를 구할 수 있습니다. 

---

My Code

for tc in range(int(input())):
    n = int(input())

    len = 1 
    i = 10  
    while i <= n:
        len += 1 
        i *= 10  
    
    result = len * (n - i // 10 + 1) 

    len = 1 
    j = 1
    while j < i // 10:
        result += len * 9 * j
        j *= 10 
        len += 1
    
    print('#' + str(tc + 1), end = ' ')
    print(result)