[백준-1790] 수 이어 쓰기 2

문제

링크

코드

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

# 수의 길이 알아내기
lng = 0
for i in range(len(str(n))) :
    if i < len(str(n))-1 :
        lng += 9 * (10**i) * (i+1)
    else :
        lng += (n - (10**i) + 1) * len(str(n))
        
def solution() : 
    # 수의 길이가 k보다 작을 때
    if lng < k :
        print(-1)
        return
    # k가 10보다 작을 때는 한 자리 수
    if k < 10 :
        print(k)
        return
    # 두 자리 수 부터
    a = 0
    for i in range(len(str(n))) :
        a = 9 * (10**i) * (i+1) + a
        b = 9 * (10**(i+1)) * (i+2)
        if a < k <= a + b :
            # 1을 빼는 이유 :
            # 배열은 0부터 시작하기 때문
            tmp = k - a - 1
            number = 10 ** (i+1) + (tmp // (i+2))
            rest = tmp % (i+2)
            print(str(number)[rest])
            return

solution()

참고한 글

• [백준][1790번][수학] 수 이어 쓰기 2

1. 수의 길이 알아내기

   한 자리 수 : 9 (1 ~ 9)
   두 자리 수 : 90 2 = 180 (10 ~ 99)
   세 자리 수 : 900 3 = 2700 (100 ~ 999) ...

i+1 자리 수일 때 이 수의 길이는

(10 ** (i+1) -1 - 10 ** i) * (i+1) 

이다.

그리고 총 길이는 한 자리 수부터 i+1자리 수 까지 합하면 된다.
이때 위의 길이들은 다 9, 99, 999, ... 등 끝까지 계산한 값이므로

(n - (10 ** i) + 1) * len(str(n)) 

으로 계산할 수 있다.

ex) 133까지 수의 길이는
9 + 90 2 + (133 - (10 ** 2) + 1) 3 = 291 이다.

2. K번째 숫자 알아내기

• k가 위에서 구해낸 수의 길이보다 작으면 구할 수 없으므로 -1 출력
• k가 10보다 작으면 한 자리 수 이므로 그대로 출력

위 조건에 맞지 않을 때 아래와 같이 해결한다.
일단 두 자리 수 이상이라는 전제 하에 풀이를 시작한다.

a = 9 * (10**i) * (i+1) + a
b = 9 * (10**(i+1)) * (i+2)

위 계산 식을 통해서 k번째 수가 몇 자리 수인지 확인한다.

a < k <= a+b 내부에 있을 경우,
해당 자리 수 이하는 필요 없으므로 빼준다.

tmp = k - a - 1

이때 1을 빼주는 이유는
예를 들어 앞에서 11번째일 때는 1부터 시작해서 11번째를 의미한다.
하지만 배열에서 0부터 시작하기 때문에 1을 빼주고 시작하는 것이다.
(일단 나는 이렇게 이해하고 문제를 풀 수 있었다.)

number = 10 ** (i+1) + (tmp // (i+2))
rest = tmp % (i+2)

예를 들어 K번째 수가 세 자리 수일 때 맨 앞 수가 100이다.
그리고 세 자리이므로 위에서 구한 값을 3으로 나눠주면 몫으로 몇 번째 숫자인지,
나머지로 몫 번째 숫자에서 몇 번째에 위치하는지 알 수 있다.

print(str(number)[rest])

이를 이용해서 K번째 자리 숫자를 출력할 수 있다.