[Backjoon] 1748 수 이어 쓰기 1 Python 문제 풀이

출처:1748 수 이어 쓰기 1

문제해석

문제를 풀기 전에 딱 보기에도 가장 반복문으로 모든 수의 자릿수를 일일이 더하는 식으로 구현을 진행하면 시간초과가 나올 것 같은 문제였다.

일반적으로 파이썬 프로그램에서는 2,000만 번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다.

코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다. 또한 연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 계산하는 것이 좋다.

응시자가 작성한 프로그램으로 모든 케이스를 통과해야만 합격으로 판단하므로 "최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.

그렇기에 이번 문제는 N의 최대 범위가 1억까지이므로 파이썬 언어로는 최악의 경우 5초까지도 걸릴 수 있다고 상정해야 한다.

그렇다면 반복문으로 구현하는 것은 애당초 논외로 두고 생각을 해보아야 한다.

반복문의 시간복잡도는 O(N)이므로 이보다 더 시간을 줄일 수 있는 알고리즘을 사용해야하므로 이 문제는 상수나 로그의 시간복잡도를 지녀야 풀 수 있는 문제라는 것을 알 수 있었다.

O(1)의 시간복잡도를 지닌 알고리즘이라 하면 수식의 형태로 나타나지는 형태이므로 해당 문제의 답을 도출해낼 수 있는 어떠한 수식으로 표현할 수 있는 문제라는 것을 예상하고 그 규칙을 찾기위해서 문제의 핵심이 될만한 부분들을 찾아본다.

이 문제의 핵심은 숫자의 자릿수이다.
1부터 9까지의 9개의 수는 1자리수이다.
10부터 99까지의 90개의 수는 2자리수이다.
100부터 999까지의 900개의 수는 3자리수이다.

세자리까지만 나열했을 때 이미 어떠한 규칙이 있는지 여기서 눈치챘었고 수식으로 만들어낼 수 있었다.

1 자리수를 모두 더하면 9(9개1자리수(1))
2 자리수를 모두 더하면 180(90개2자리수(2))
3 자리수를 모두 더하면 2700(900개*3자리수(3))

이는 910^(자리수-1)자리수와 같다.

따라서 구하고자 하는 수의 자리수보다 한자리 이전의 수들을 더한 값들에 구하고자 하는 자리수의 수를 계산해주면 된다.

해답코드

import sys

n = sys.stdin.readline().rstrip()

leng = len(n)
ans = 0

for i in range(1,leng):
    ans += 9*10**(i-1)*i

ans += (int(n)-10**(leng-1)+1)*leng

print(ans)