💡 문제
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다.
출력
첫째 줄에 앞에서 k번째 자리 숫자를 출력한다. 수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우는 -1을 출력한다.
💭 접근
당연하게도 단순하게 수를 이어붙이면 메모리초과가 발생한다.
그렇다면 이 각 숫자의 자릿수와 각 자릿수에 해당하는 숫자의 개수를 활용해서 문제를 해결할 수 있다.
- 한자리 숫자는 9개이다.
- 두자리 숫자는 90개이다.
- 세자리 숫자는 900개이다.
한번 입력 k가 300으로 주어졌다고 가정하고 문제를 해결해보자.
먼저 300번째 수가 몇자리 수의 일부인지 확인해야 한다.
while k > nine * digit:
k -= digit * nine
start += nine
nine *= 10
digit += 1따라서 300 - 90 * 2 - 9 * 1 = 111이고, 이는 300번째 숫자가 세자리 숫자 중 111번째 숫자라는 것을 알았다..
그렇다면 111번째 숫자를 포함하고 있는 정수를 찾아야한다. 우선 start = 99인 상태이므로 +1을 해주면 세자리 숫자의 시작(100)이 되게 된다.
이제 111을 사용해서 세자리 숫자 중 몇번째 정수인지를 구하면 된다.
ans = start + 1 + (k - 1) // digit이때 start = 100이고, (k - 1) // digit = 36이므로 111번째 숫자는 136의 일부인 것을 알 수 있다.
여기서 세자리 숫자 중 111번째 숫자를 포함하는 정수를 구하기 위해 k에 -1을 한 값에서 몫을 구하였는데 왜 그랬을까?
일반적으로 코드 상에서 문자열의 인덱스는 1이 아닌 0부터 시작한다.
그러나 문제에서는 문자열의 인덱스가 (1번째, 2번째, ...) 와 같이 1부터 시작하므로 1을 빼서 코드 상의 인덱스와 맞춰준 것이다.
이제 정수 136에 포함되어 있는 1, 3, 6 중 하나라는 것을 알았고,
str(ans)[(k - 1) % digit]위처럼 이번엔 모듈러 연산을 통해 136 중 몇번째 숫자인지 구하고, 이를 인덱스로 사용하여 정답(6)을 도출해 낼 수 있다.
📒 코드
n, k = map(int, input().split())
start = 0
digit = 1
nine = 9
while k > nine * digit:
k -= digit * nine
start += nine
nine *= 10
digit += 1
ans = start + 1 + (k - 1) // digit
if ans > n:
print(-1)
else:
print(str(ans)[(k - 1) % digit])💭 후기
k에서 -1을 하는 이유를 이해하는데에 시간이 많이 걸렸다.
조금만 생각해보면 바로 알 수 있었던 것 같은데...
🔗 문제 출처
https://www.acmicpc.net/problem/1790
