BOJ 12755 - 수면 장애

문제

1, 2, 3, ... 을 이어 쓴 무한 문자열 "123456789101112..."에서 N번째 숫자를 구하라.

입력

N이 주어진다 (1 <= N <= 2^31 - 1).

출력

N번째 숫자를 출력한다.

예제

입력	출력
`15`	`2`

풀이

자릿수별로 차지하는 문자 수를 계산하여 N이 속하는 자릿수 범위를 찾고, 해당 수의 특정 자릿수를 반환한다.

k자리 수는 9 * k * 10^(k-1)개의 문자를 차지한다
N에서 이전 자릿수들의 문자 수를 빼가며 해당 자릿수를 찾는다
target = start + (N-1) // digits로 해당 수를, index = (N-1) % digits로 자릿수 위치를 구한다

핵심 아이디어: 자릿수별 문자 수를 누적하면 O(log N)에 정확한 위치를 계산할 수 있다.

코드

n = int(input())
 
digits = 1
while n > 9 * digits * 10 ** (digits - 1):
    n -= 9 * digits * 10 ** (digits - 1)
    digits += 1
start = 10 ** (digits - 1)
target = start + (n - 1) // digits
index = (n - 1) % digits
 
print(int(str(target)[index]))

복잡도

시간: O(log N)
공간: O(1)

문제