[백준] 1790번. 수 이어 쓰기 2(JAVA)

문제

https://www.acmicpc.net/problem/1790

---

풀이(42분)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 자연수 범위 (1 ~ n)
        long k = Long.parseLong(st.nextToken()); // 찾고자 하는 k번째 숫자

        System.out.println(findKthDigit(n, k));
    }

    // k번째 숫자의 자릿수를 찾는 함수
    private static int findKthDigit(int n, long k) {
        long digitLength = 1;  // 현재 자릿수 (1자리, 2자리, ...)
        long rangeCount = 9;   // 해당 자릿수에서 가능한 숫자의 개수 (1자리: 9개, 2자리: 90개, ...)

        // k가 현재 자리수 범위 내에서 존재하는지 확인
        while (k > digitLength * rangeCount) {
            k -= (digitLength * rangeCount); // 해당 자리수의 모든 숫자를 건너뜀
            digitLength++;                   // 자리수 증가
            rangeCount *= 10;                 // 숫자 개수 업데이트
        }
        k--;  // 0-based index로 변환

        long targetNumber = (long) Math.pow(10, digitLength - 1) + (k / digitLength); // k번째 숫자가 포함된 실제 숫자

        if (targetNumber > n) return -1; // 숫자가 n을 넘어가면 존재하지 않음

        return getDigitFromNumber(targetNumber, (int) (k % digitLength));
    }

    // 특정 숫자의 원하는 자릿수를 반환하는 함수
    private static int getDigitFromNumber(long number, int digitIndex) {
        return String.valueOf(number).charAt(digitIndex) - '0';
    }
}

---

문제 풀이 전략

 

1. 자릿수가 1인 숫자를 먼저 고려

• 1부터 9까지 총 9개 숫자가 존재하므로, 1자리 숫자는 9개이다.
• 만약 K ≤ 9라면 K번째 숫자는 그대로 찾을 수 있다.
• 하지만 여기서는 K = 23이므로, 1자리 숫자는 건너뛸 수 있다.

2. 2자리 숫자로 이동

• K - 9 = 14를 계산하여, 2자리 숫자에서 14번째 숫자를 찾아야 함을 확인한다.
• 2자리 숫자는 10부터 시작하며, 각 숫자는 2개의 자릿수를 갖는다.

3. 몇 개의 숫자를 건너뛸지 계산

• 14번째 숫자를 찾으려면, (14 - 1) / 2를 계산한다.
  • 14 - 1 = 13 (K를 0부터 시작하는 인덱스로 변환)
  • 13 / 2 = 6 (몫: 건너뛸 숫자의 개수, 나머지: 해당 숫자의 몇 번째 자리인지)
• 즉, 10부터 6개 숫자를 건너뛴다 → 10, 11, 12, 13, 14, 15까지 건너뛰고 16에서 찾으면 된다.

4. K번째 숫자 찾기

• 16의 **인덱스 1(두 번째 자리)**를 가져오면 **"6"**이 정답이 된다.

5. 숫자가 범위를 초과하는 경우 처리

• 만약 K번째 숫자가 존재하지 않으면 -1을 출력한다.
• 즉, 숫자 N이 K번째 자리보다 작다면 -1을 반환하면 된다.