[LeetCode] 400. Nth Digit(Java, 순서 찾기, N번째 숫자 찾기, 코딩테스트)

## 접근방법

---

이 문제는, 1부터 2^31 - 1까지 나열했을 때, N번째 숫자를 찾는 것이다. 10번째 숫자는, 10에서 1을 의미한다. 이제 규칙을 찾아서, N번째 숫자를 찾아야 한다.

 

 

 

N의 범위가 2^31 - 1이므로, 모든 숫자를 확인하면서 자리수를 확인하면 시간초과가 발생할 것이다. 자리수의 규칙을 찾아보자.

 

 

 

1 ~ 9는 한 자리수, 9개

10 ~ 99는 두 자리수, 90 * 2개

100 ~ 999는 세 자리수, 900 * 3개

 

 

 

위와 같은 규칙이 성립한다. 위의 규칙을 이용하면 N이 적어도 몇 자리수인지 파악이 가능하다. 개수를 누적합하면서, 구간을 찾으면 몇자리수인지 확인할 수 있다. 

 

 

 

 

 

위의 그림을 보면서 규칙을 파악해보자. 현재 두 자리수는 10번째부터 시작한다. 몇번째부터 시작하는지는 N - 1자리수까지 개수의 합을 의미한다. N자리수는 모두 N자리인 숫자들로 이루어져 있다는 점을 이용해서, 13번째 자리수를 구해보자.

 

 

 

10 + (13 - 10) / 2 = 11, (13 - 10) % 2 = 1

 

 

 

위의 두식은 11에서 1번째 자리를 의미한다. 따라서, 13번째 자리수는 1이 된다. 위의 식을 공식화하면,

 

 

 

(N - 1자리수까지 개수의 합 + 1) + (n - (N - 1자리수까지 개수의 합 + 1)) / N이 찾는 숫자를 담고 있는 수를 의미하고,

 

 

 

.(n - (N - 1자리수까지 개수의 합 + 1)) % N이 찾는 숫자를 의미한다.

 

 

 

모든 N자리수에서 해당되므로, 이를 일반화하고 코드를 작성하면 된다.

 

 

## 해설코드

---

class Solution {
    public int findNthDigit(int n) {
        if(n < 10) return n;
        
        long num1 = 9;
        long num2 = 1;
        long sum = 9;
        
        while(n >= (num1 * 10) * (num2 + 1)){
            num1 *= 10;
            num2 += 1;
            sum += num1 * num2;
        }
 
        n -= (sum + 1);
        String str = String.valueOf((int)Math.pow(10, num2) + n / (num2 + 1));        
        return str.charAt(n % ((int)num2 + 1)) - '0';
    }
}