[Algorithm] 연속된 숫자열에서 n번째 문자 알아내기
[문제] 1부터 숫자가 연속된 문자열(12345678910111213...)이 있을때 n번째 숫자는 뭘까?
답변 예시
| n | answer |
| 1 | 1 |
| 9 | 9 |
| 10 | 1 |
| 11 | 0 |
1. 단순무식한 효율무시 알고리즘
아주 단순히 생각해 보면 연속된 문제열을 만드는것은 쉽고 문자열을 만든후 n번 문자를 찾는 알고리즘을 구현해 보겠다.
int num_of_pos_1(int n){
string str;
for(auto i=1;i<=n;i++){
str += std::to_string(i);
if(str.length() > n){
break;
}
}
return str[n-1] - '0';
}
n이 늘어 나면 늘어 날수록 memory와 cpu비용이 함께 증가하는 아주 안좋은 알고리즘 되겠다.
int to string역시 O(n)이므로 사실상의 시간 복잡도는 O(n^n)이다.
그러나
이걸 아키텍처 적으로 플어본다면 문자열 str은 상수와가 가능하고 상수화하고 n번째 문자를 찾는다면 결국은 O(1)의 완벽한 알고리즘이된다. 상황과 시스템에 따라서 이런 알고리즘도 상당한 퍼포먼스를 발휘할수도 있다. 만약 str을 생성하는 문제가 복잡하고 수식으로 계산하기 힘든경우에는 웜업시간에 str을 생성하고 매 요청때마다 결과를 도출하는것도 사실상 더 많이 쓰이는 방법되겠다.
그래도 알고리즘만 연구하시는 분들은 최적의 공간/시간 복잡도를 추구하므로 최적의 공간/시간 복잡도를 가지는 알고리즘을 연구해보자!!
2. 수치해석적 알고리즘
- 일단 문제를 해결하기 위해서 규칙을 찾아내야한다.
- 문자열을 만드는 숫자를 "k"라고 하고 요구하는 위치값을 "n"이라하자.
- k의 자릿수를 digit이라하자
- 각 digit별 자리수 count(digit) = 9 * 10 ^ (digit-1) 이다.
위의 정의에 의해서 n의 변위 N을 구해보면 아래와 같다
k(digit, k범위) = N(digit, n의 범위)
k(1, {1...9}) = N(1, {1, 2, 3...9})
k(2, {10..99}) = N(2, {10,11,12,13,...,188,189})
k(3, {100...999}) = N(3, {190,191,192,...,2887, 2888, 2889})
digit 구하기
위의 분석에 의거하여 digit은 N(digit)안에 있다이다.
시작 N(digit) <= n <= 종료 N(digit)
이 규칙에 의거하여 digit값을 구해보자
int digit(int n){
int digit = 1;
int count = 9;
int end = 9;
while(n > end){
digit++;
count *= 10;
end += count * digit;
}
return digit;
}
각 digit별 count(digit)는 9 * 10 ^ (digit-1)이라는점에 착안하여 구지 end라는 변수가 필요할까 고민해 본다.
int digit2(int n){
int digit = 1;
int count = 9;
while(n > digit * count){
n -= digit * count;
digit++;
count *= 10;
}
return digit;
}
k 구하기
k의 digit별 시작값 Ks(digit) = 10 ^ (digit-1) 이다.
시작값을 구했는데 변화량은 어떻게 구할까?
약간 정규화 해보자. 각 구간별로 시작값으로 n값을 빼면 모두 0부터 시작한다.
n: (1, 2, 3...9) - 1 = N(0, 1, 2,...,8)
n: (10, 11, 12, 13,...,188,189) - 10 = N(0, 1 ,2, 3,...,178, 179)
n: (190, 191, 192,...,2887, 2888, 2889) - 190 = N(0, 1 ,2,...,2697, 2698, 2699)
결국은 n - Ks(digit)이 변화량이다. 이를 digit으로 나누면 k의 변화량이 된다.
일단 Ns(digit) = Ns(1) + ... + Ns(digit)을 구해보자
int nstart(int digit){
int ns = 1;
int count = 9;
for(int i=0;i<digit-1;i++){
ns += count * (i + 1);
count *= 10;
}
return ns;
}
이를 이용해서 k값을 구하면
int cal_k(int n){
int digit = digit2(n);
return (int)pow(10, digit-1) + (int)(n - nstart(digit))/digit;
}
결국 위와 같이 필요한 변수값들을 구해봤는데 각각의 알고리즘은 digit으로 묶여 있기 때문에 결국은 하나로 합쳐진다.
int cal_k2(int n){
int digit = 1;
int count = 9;
int ks = 1;
while(n > digit * count){
n -= digit * count;
digit++;
count *= 10; // 9 * 10 ^ (digit - 1)
ks *= 10; // 10 ^ (digit - 1)
}
// n이 결국은 ns로 부터의 변화량값임 ( 0부터 시작하도록 -1을 해준다 )
return ks + (n - 1)/digit;
}
n번째 숫자구하기 (결론)
결국 위와 같이 필요한 변수값들을 구해봤는데 각각의 알고리즘을 구성해 봤는데 이를 하나로 합쳐보겠다.
int num_of_pos_2(int n){
int digit = 1;
int count = 9;
int ks = 1;
while(n > digit * count){
n -= digit * count;
digit++;
count *= 10; // 9 * 10 ^ (digit - 1)
ks *= 10; // 10 ^ (digit - 1)
}
// n이 결국은 ns로 부터의 변화량값임 ( 0부터 시작하도록 -1을 해준다 )
int k = ks + (n - 1)/digit;
return std::to_string(k)[(n-1)%digit] - '0';
}