무한히 이어지는 정수 수열이 하나 있다고 가정해 봅시다. 이때 이 수열에서 n번째 자릿수가 무엇인지 찾아야 합니다. 예를 들어 입력이 11이라면 출력은 0입니다. 숫자들을 123456789101112처럼 차례대로 이어 붙였을 때 11번째 자리의 숫자가 0이기 때문입니다.
문제 해결 접근 방법
이 문제는 모든 숫자를 직접 나열하지 않고도 효율적으로 풀 수 있습니다. 핵심 아이디어는 한 자리 수(1~9), 두 자리 수(10~99), 세 자리 수(100~999)처럼 자릿수 구간별로 전체 자릿수 개수를 누적해 가면서, n번째 숫자가 어느 구간에 속하는지 찾는 것입니다. 알고리즘은 다음 단계로 진행됩니다.
- len := 1, cnt := 9, start := 1로 초기화합니다.
- n > len * cnt 인 동안 다음을 반복합니다.
- n := n − (len * cnt)
- cnt := cnt * 10, start := start * 10
- len을 1 증가시킵니다.
- start := start + (n − 1) / len 으로 목표 숫자가 위치한 실제 값을 구합니다.
- s := start를 문자열로 변환합니다.
- s[(n − 1) mod len] 을 반환합니다.
이 방식은 반복문이 자릿수 길이만큼만 돌기 때문에 시간 복잡도가 O(log n)으로 매우 효율적입니다.
예제 코드 (C++)
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int findNthDigit(int n) {
lli len = 1;
lli cnt = 9;
lli start = 1;
while(n > len * cnt){
n -= len * cnt;
cnt *= 10;
start *= 10;
len++;
}
start += (n - 1) / len;
string s = to_string(start);
return s[(n - 1) % len] - '0';
}
};
main(){
Solution ob;
cout << (ob.findNthDigit(11));
}
입력
11
출력
0
위 예제에서 n = 11일 때, 한 자리 수 구간에는 9개의 자릿수가 있으므로 이를 제외하면 두 자리 수 구간의 2번째 자릿수를 찾게 됩니다. 두 자리 수는 10부터 시작하므로 해당 위치의 숫자는 10의 두 번째 자리인 0이 되어 최종적으로 0이 출력됩니다.