[백준 #1790] 수 이어 쓰기 2 - Python(파이썬)

문제

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

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

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.

해설

모든 수를 이어 붙여서 k번째 자리 숫자를 찾는다면 time out이 발생한다. 그래서 앞에서 생략할 수 있는 수들을 생략하면서 찾아야 한다.

k번째 이전에 생략해도 되는 자릿수(digit)을 찾고 지금까지 이어붙인 숫자의 길이 합(total)을 찾아서 최대한 생략할 수 있는 수는 생략해야 한다.

코드

import sys

input = sys.stdin.readline

n, k = map(int, input().split(' '))

# 1. 몇 번째 자리수인지 확인
digit = 1  # 현재 자리수 (예: 1자리, 2자리, ...)
count = 9  # 해당 자리수에 있는 숫자의 개수 (1자리수는 9개, 2자리수는 90개, ...)
total = 0  # 지금까지 이어붙인 숫자의 길이 합
start = 1  # 현재 자리수에서 시작 숫자 (1자리수는 1, 2자리수는 10, 3자리수는 100, ...)

while k > total + digit * count:
    total += digit * count
    digit += 1
    count *= 10
    start *= 10

offset = k - total - 1
part_of_number = offset // digit
number = start + part_of_number
pos = offset % digit

answer = str(number)[pos] if n >= number else -1

print(answer)