Leetcode Java Nth Digit

문제

Link

코드

class Solution {

  public int findNthDigit(int n) {
    int length = 1;
    int base = 1;
    while (n > 9L * base * length) {
      n -= 9 * base * length;
      length++;
      base *= 10;
    }
    int result = 0;
    int num = (n - 1) / length + base;
    for (int idx = (n - 1) % length; idx < length; idx++) {
      result = num % 10;
      num /= 10;
    }
    return result;
  }

}

결과

Link

설명

1. 무한 정수 시퀀스에서 주어진 정수인 n번째 값을 반환한다.
   • n이 11인 경우, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, … 중 0을 반환한다.

2. 길이를 저장하는 length와 배수를 결정하는 base에 1을 넣어 초기화한다.

3. n이 $9 \times base \times length$ 초과일 때 까지 반복하여 length와 base를 계산한다.
   • n에 $9 \times base \times length$을 빼주고, length를 1 더하고 base를 10 곱해준다.
     • 해당 무한 정수 시퀀스는 아래와 같은 규칙이 성립한다.
     • 1 ~ 9 = $9 \times 1 = 9$ 자리
     • 10 ~ 99 = $90 \times 2 = 180$ 자리
     • 100 ~ 999 = $900 \times 3 = 2700$ 자리
     • 위 규칙을 이용하여 숫자 범위를 추정하기 위해 $9 \times base \times length$를 정의하고, base는 10단위, length는 1 단위로 계속 증가시킨다.
4. 결과를 넣을 result에 0을, 계산에 필요한 num에 $\frac{n - 1}{length} + base$을 넣어준다.
   • num의 초기 값의 설정을 통해 무한 정수 시퀀스에서 n번째 위치에 포함되는 숫자를 유추한다.
5. $(n - 1) % length$의 결과부터 length 까지 idx를 증가시키며 result를 유추한다.
   • result에 num을 10으로 나눈 나머지 값을 넣어주고, num을 10으로 나누어준다.
6. 반복이 완료되면 무한 정수 시퀀스에서 n번째 값이 저장된 result를 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.