[백준] 1748: 수 이어 쓰기 1 (Python)

1748: 수 이어 쓰기 1

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

1748번: 수 이어 쓰기 1

문제

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

1234567891011121314151617181920212223...

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

입력

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

출력

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

풀이

 n의 범위가 딱 1억까지이므로 브루트 포스를 아슬아슬하게 사용할 수 있을 것 같았다. 그래서 1부터 n까지의 수를 이어 썼을 때 길이를 반복문을 통해 구하고자 했다. while루프를 이용해 구상해본 코드 초안은 다음과 같다.

index = 1
while(index <= n):
    if 1 <= index <= 9:
        count += 1
    elif 10 <= index <= 99:
        count += 2
    ...
    index += 1

 그런데 이 방법은 1부터 1억까지 범위를 하나하나 if문으로 지정해줘야 하는데다가 코드가 불필요하게 길었다. index 변수의 범위와 count의 관계를 잘 생각하면 for문을 이용해 둘을 단순한 식으로 표현할 수 있을 것 같았다. 오랜 시간 고민한 끝에 range(10^(i-1), 10^i) 에 대해 count += i를 수행하면 된다는 것을 깨달았다. 이때 n까지만 더할 수 있도록 n에 도달하면 반복문을 멈추게 하였고, i의 범위는 1부터 n의 log10 + 2로 계산했다. 이렇게 작성한 전체 코드는 다음과 같다. 

import math, sys
n = int(sys.stdin.readline())
count = 0
for i in range(1, int(math.log10(n)) + 2):
    for j in range (10**(i-1), 10**i):
        count += i
        if j >= n: 
            break
print(count)

 처음에 코드를 제출했을 때 시간초과가 났다. input()을 readline()으로 바꿔보았지만 당연히 계속 시간초과가 났다. 그래서 언어를 Python에서 PyPy3으로 바꾸었더니 시간초과 없이 정답 판정을 받을 수 있었다. 이 코드의 연산은 readline 1번, log10() 1번, count += i 연산이 n번, j>=n 비교 연산도 n번 수행되는데 어떻게 손봐야 Python에서도 시간초과가 나지 않을지 감이 오지 않았다. 본질적으로 다른 접근이 필요해 보였다. 

 그래서 다른 풀이를 찾아본 결과 각 자릿수의 길이를 확실하게 알 수 있다는 점을 이용해 가장 높은 자릿수와 그 직전까지의 합을 나누어 구한다는 것을 깨달았다. 예를 들어 n이 123이라면 1*9 + 2*90 + 3*24이 되는 것이다. 그리고 또 하나 놀라운 사실을 발견했는데, 나는 자릿수를 상용 로그 함수를 이용하여 계산하였지만 len() 함수를 이용하여 계산하는 방법도 있었다는 것이다. 훨씬 간단한 아이디어인데 왜 생각하지 못했을까 싶었다. 이 아이디어를 이용한 코드는 다음과 같다.

n = input()
length = len(n) - 1
result = 0
for i in range(length):
    result += (9 * (10 ** i)) * (i + 1) # i+1번째 자릿수의 숫자 개수 * 길이
result += ((int(n) - (10 ** length)) + 1) * (length + 1) # 가장 높은 자릿수의 숫자 개수 * 길이
print(result)

 최대 1억번 연산해야 했던 이전 풀이와 달리 이 풀이는 최대 9번만 연산하면 되기 때문에 훨씬 시간과 메모리가 줄어든 것을 확인할 수 있었다. 덧붙이자면 이 문제의 여러 풀이의 시간복잡도에 대한 부분은 https://cjleee.tistory.com/10 블로그의 도움을 받아 쉽게 이해할 수 있었다.