[BOJ] 수 이어 쓰기1 in Python

문제 풀러 가기!

문제는 어렵지 않았습니다. 규칙성을 찾아서 코드만 짜주면 끝이었습니다. 그래도 일단 중요한 것은 입력값이 1억까지이기 때문에 그냥 막짜면 시간 초과가 날거에요. 그렇기 때문에 규칙을 찾아야 합니다.

제가 푼 아이디어는 다음과 같습니다.

문제에서 주어지는 숫자는 10진법이기 때문에, 수를 받으면 10부터 시작하여 10의 제곱, 10의 세제곱.... 10의 거듭제곱을 받은 숫자보다 넘지 않는 상태까지 계속 비교하면서 해당 숫자의 길이를 계속 더해야합니다. 예를 들어서 101 을 받았다고 해볼게요.

그냥 완전히 for문으로 돌려버리면, 101번을 연산해야합니다. for문 연산 101번, 더하는 연산 101번.. 그리고 문자열로 더해야하기 때문에, 연산 횟수는 더 많아지겠죠.

10 <= 101 -> answer에 1 ~ 9의 숫자를 모두 더합니다. 이때 당연히 숫자의 길이만을 더해야겠죠.

100 <= 101 -> answer에 10 ~ 99의 숫자 길이를 모두 더합니다.

1000은 성립이 안되기 때문에

answer에 100 ~ 101의 숫자의 길이를 모두 더합니다.

그러면 1억까지의 입력값을 최소 10번 순회를 해도 모두 끝나게 됩니다.

애초에 이 문제는 시간 제한이 0.15초이기 때문에 정말정말 빨리 끝내는 코드를 작성해야 합니다..

그래서 위와 같은 아이디어를 활용하여 제가 작성한 코드는 다음과 같아요.

import sys

number = int(sys.stdin.readline().strip())
i = 1
answer = 0

while True:
    if 10**i <= number: answer += ((10**i) - (10**(i-1))) * i
    else:
        answer += (number - (10**(i-1)) + 1) * i
        break
    i += 1

print(int(answer))