[Python][Silver 4][1748] 수 이어쓰기 1

|    문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

 

|    입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

 

 

|    출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

 

 

---

정답 코드

import sys
input = sys.stdin.readline

class Solution:
    # 메모리 초과
    def relay_number_(self):
        n = int(input())
        nums = ''.join(map(str, range(1,n+1)))
        print(len(nums))
    # 시간 초과
    def relay_number__(self):
        n = int(input())
        res = 0
        for i in range(1, n+1):
            res += len(str(i))
        print(res)

    def relay_number(self):
        n = input().strip() # 12
        x = len(n) # 2
        res = 0
        for i in range(1, x):
            res += 9 * i * (10**(i-1))
        
        res += (int(n) - 10**(x-1) + 1) * x
        print(res)

if __name__ == "__main__":
    s = Solution()
    s.relay_number()

 

 

|    비고

0.15초의 시간 제한이 있는 문제라서 일반적인 방식으로는 메모리 초과와 시간 초과를 피할 수 없었다. 구글링을 하던 중 규칙을 발견할 수 있게 되었다.

먼저, 1부터 9까지는 한 자리 숫자이기 때문에, 예를 들어 입력값이 9라면 9자리 숫자가 된다. 두 자리 숫자는 10부터 99까지 총 90개 이므로 입력값이 99라면 9 + 90 * 2 = 189가 출력값이 된다. 만약 n의 자릿수를 x라고 한다면, 이전(x-1) 자릿수 9 * x * 10 ** (x-1) 공식에다가 현재(x) 자릿수 공식인 (n - 10**(x-1) + 1) * x를 더한 값이 출력값이 된다.

예를 들어, 12의 경우 자릿수는 2이며, 이전 한 자릿수 9 * 1 * 10 ** 0 = 9에다가, 현재 자릿수 공식인 (12 - 10**1 + 1) * 2  = 6을 더하여 답이 15가 된다. 

123456789101112