[백준] 1748번 수 이어 쓰기 1

유튜브에 T아카데미 채널에 있는 동영상 중 "기초 알고리즘과 파이썬 코딩"을 보고 문제 해결 절차를 따라 해보았다.

우선 기본적으로 문제를 확인한다. 시간과 용량은 어떻게 되며, 입력 값이 있다면 그 값은 얼마나 되는지 파악해야 한다.

이 문제의 입력값은 N(1≤N≤100,000,000) 이렇게 주어진다. 

Python / 1sec	설명
1,000,000	안정적
10,000,000	대다수 가능
100,000,000	거의 불가능

강의에서 나온 기준으로 1sec에 1억번 연산을 수행하면 거의 불가능한 수준으로 볼 수 있다. 그럼 이 경우에 O(N)의 시간복잡도가 되면 문제를 풀지 못한다는 이야기다.

이 문제를 풀기 위해서 O(1) or O(logN), O(√n)의 시간 복잡도를 가져야 하는 것을 파악하고 문제를 풀어보자

우선 Native한 풀이를 떠올린다(특정 제한과 무관하게)

n = int(input())
print(sum(map(lambda x: len(str(x)), range(1, n+1))))

위 코드처럼 작성할 수 있지만, 시간 복잡도가 O(NlogN)이 된다. N만큼 반복하지만 str()의 시간 복잡도가 logN이다.

그럼 다른 방법을 생각해야 한다. n=120일 경우를 생각해보자.

수의 특징을 보면

1, 2, 3, ····, 9
10, 11, 12, ····, 99
100, 101, 102, ····, 120

100의 자리를 가지는 수의 개수 100~120으로 120-100+1=21
10의 자리를 가지는 수의 개수 10~99로 120-10+1 = 111
1의 자리를 가지는 수의 개수 1~9로 120-1+1 = 120
(이해를 돕기 위해 거꾸로 적었다.)

n = int(input())
res, i = 0, 1
while i <= n:
    res += n-i+1
    i *= 10
print(res)