[백준 / 파이썬] 백준 1748번 문제 풀이: 수 이어 쓰기 1

 

문제

---

 

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

1234567891011121314151617181920212223...

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

 

입력

---

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

 

출력

---

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

 

 

문제 해결

---

문제 해결 방법에는 2가지가 있다.

 

첫번째 방법은 숫자를 0에서부터 N(입력값)까지 모든 숫자에 대해 자릿수를 모두 더 하는 방법이다.

이 방법은 O(n)의 시간복잡도로 직관적이긴하나 비효율적인 방법이다.

import sys
N=int(sys.stdin.readline())
answer=0
while N!=0:
    answer+=len(str(N))
    N-=1
print(answer)

 

 

두번째 방법은 1부터 9까지 10부터 99까지 ... 구간을 나누어서 자릿수를 한번에 구하는 방법이다.

예를 들어

n=120일 때,
1,2,3,4,5,6,7,8,9 -> 1자리씩 총 9
10,11,12,...,99 -> 각 2자리씩 총 90 * 2 = 180

100,101,102,...,120-> 각 3자리씩 총 21 * 3= 63
최종 합 = 9 + 180 + 63 = 252

 

이방법은 O(logn)의 시간 복잡도를 갖는다.

첫번째 방법보다 효율적인 방법으로 답을 구할 수 있다.

 

전체 코드

import sys

def count_total_digit_length(n: int) -> int:

    total_length = 0
    power = 0

    # 10^power 자릿수를 사용하는 숫자 범위를 넘지 않을 때까지 반복
    while n // (10 ** power) >= 10:
        total_length += 9 * (10 ** power) * (power + 1)
        power += 1

    # 남아 있는 범위(10^power 이상부터 n까지)에 대한 자릿수 계산
    total_length += (n - 10**power + 1) * (power + 1)
    return total_length

def main():
    n = int(sys.stdin.readline().strip())
    print(count_total_digit_length(n))

if __name__ == "__main__":
    main()

 

부분 설명

while n // (10 ** power) >= 10:
        total_length += 9 * (10 ** power) * (power + 1)
        power += 1

while 의 조건식은 위의 예시에서 10 과 100을 구분하는 장치이다. 100에서는 120까지 채우지 못하기 때문에 따로 계산할 필요가 있다. 반면 1은 9까지, 10은 99까지의 모든 숫자가 채워졌으므로 각각 9개, 180개의 자릿수가 필요하다는 것을 바로 알 수 있다.

 

# 남아 있는 범위(10^power 이상부터 n까지)에 대한 자릿수 계산
    total_length += (n - 10**power + 1) * (power + 1)

 

위의 예시에서 100부터 120까지의 필요한 자릿수를 계산하는 과정이다. (120-100+1)*3=63 이라는 결과를 얻을 수 있다.