[백준] 1748번 수 이어 쓰기 1(Python - 파이썬)

백준 1748번문제입니다. (solved.ac) 기준 실버 3문제입니다.

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

1748번: 수 이어 쓰기 1

 

예제 입력 1 : 5 / 출력 : 5

예제 입력 2 : 15 / 출력 : 21

예제 입력 3 : 120 / 출력 : 252

 

문제를 읽고 아주 간단한 문제라고 생각을 하고... 그냥 손이 가는대로 작성한 첫번째 코드입니다.

x = int(input())

a = []
for i in range(1, x+1) :
    a.append(str(i))

a = "".join(a)

print(len(a))

아주 단순한 생각으로 리스트에 숫자(문자열로 변환후)를 하나씩 넣고 문자열로 합친 후 그 길이를 구하도록 코드를 작성하였습니다. 3가지의 예제 모두 정답이 잘 출력되길래 제출을 해보았더니 메모리 초과 오류가 발생하였습니다. 문제에서 N의 범위를 100,000,000까지 지정해 주었기 때문에... 위의 코드처럼 문자열들을 쭉~ 이어붙인다면 굉장히 긴 문자열이 되어 메모리 초과 오류가 발생한 것 같습니다.

 

두번째로 작성한 코드 또한 아주 간단하게 생각하고 작성하였습니다.

import sys
x = int(sys.stdin.readline().rstrip())
a = 0

for i in range(1, x+1) :
    a += len(str(i))

print(a)

이번에는 반복문을 사용하여 문자열의 길이를 즉각즉각 더하여 주도록 코드를 작성하였습니다. 이 방법은 시간 초과 오류가 발생하였습니다.

문제에서 N의 범위를 100,000,000까지 지정해 주었기 때문에...  저만큼의 반복된 연산을 하면 굉장히 오랜시간이 걸릴 것이 분명했습니다(시간 초과 오류).

 

세번째로 작성한 정답 코드입니다.

# 설명 예시는 x = 120으로 입력값을 지정해주겠습니다.
# 입력 받은 문자열의 길이를 먼저 파악한 후 길이 - 1만큼의 자릿수까지는 먼저 계산을 해줍니다.
# 예를 들어 세 자릿수 이면 한 자릿수, 두 자릿수는 미리 계산을 하고 세 자릿수는 따로 계산을 해줍니다.

import sys
x = sys.stdin.readline().rstrip() # x = '120' / len(x)는 3 ('120')
ans = 0

# 한 자릿수는 1 ~ 9, 두 자릿수는 10 ~ 99, 세 자릿수는 100 ~ 999
# 한 자릿수를 모두 더하면 9(9가지 * 자릿수(1)), 두 자릿수를 모두 더하면 180(90가지 * 자릿수(2))
# 세 자릿수를 모두 더하면 2700가지(900가지 * 자릿수(3))와 같이 규칙을 발견할 수 있습니다.

# 한 자릿수와 두 자릿수를 먼저 계산해줍니다.
for i in range(1, len(x)) :
    # 9 * 자릿수(1) i가 1인경우
    # 90 * 자릿수(2) i가 2인경우
    # 한 자릿수, 두 자릿수를 모두 더한 값을 ans에 더하여 줍니다.
    ans += int('9' + (i - 1) * '0') * i

# 한 자릿수, 두 자릿수의 계산은 미리해주었으므로
# 100 부터 120 까지(세 자릿수)의 계산을 해주면 됩니다.
# 100 부터 120 까지 갯수에 * 자릿수(3)
ans += (int(x) - 10 ** (len(x) - 1) + 1) * len(x)

print(ans)

1748번 문제를 풀며 문제에서 정해주는 입력값의 범위 등을 고려하여 메모리, 시간 초과 부분 또한 고려하여 문제를 풀어야 한다는 교훈을 얻게되었습니다.