[BaekJoon] 1790 수 이어 쓰기 2 (Java)

1.  문제 링크

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

2.  문제

요약

• 1부터 N까지의 수를 이어서 쓰면 새로운 수를 하나 얻을 수 있는데, 이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000,000보다 작거나 같은 N과 1보다 크거나 같고 1,000,000,000보다 작거나 같은 k가 주어집니다.
• 출력: 첫 번째 줄에 앞에서 k번째 자리 숫자를 출력합니다. 수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getKthNum(int n, int k) {
		long cur_position = k;
		long len = 1;
		long count_num = 9;
		long digit = 0;
		while(cur_position > count_num * len) {
			cur_position -= count_num * len;
			digit += count_num;
			count_num *= 10;
			len++;
		}
		digit = (digit + 1) + ((cur_position - 1) / len);
		if(digit > n) {
			return -1;
		} else {
			int idx = (int)((cur_position - 1) % len);
			return Character.getNumericValue(String.valueOf(digit).charAt(idx));
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		br.close();
		int n = Integer.parseInt(input[0]);
		int k = Integer.parseInt(input[1]);
		Main m = new Main();
		bw.write(m.getKthNum(n, k) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 숫자를 이어붙일 때, 한 자리 수는 총 9개, 두 자리 수는 총 90개, 세 자리 수는 총 900개라는 것을 알 수 있습니다.
• 즉, 자리 수가 하나 증가할 때마다 10배가 된다는 것을 알 수 있습니다.
• 이를 이용하여, 주어진 k가 어떤 자리 수에 속하는지 구할 수 있습니다.
• k가 속하는 자리 수 이전까지의 총 개수를 k에서 빼주고 남은 k에 대해 해당 자리에 어떤 수가 들어가는지 확인합니다.
• 현재 자리 수 전까지 지난 수의 개수들을 digit이라고 한다면 현재 자리 수 바로 이전까지 지나온 개수가 digit이기 때문에 자리 수를 맞춰주기 위해 digit에 1을 더해줍니다.
• digit에서 1을 더해줬기 때문에 한 자리를 이동한 것이므로 남은 k에서 1을 빼줍니다.
• 남은 k를 k에 해당하는 자리 수로 나눈 것의 몫은 k에 해당하는 자리 수만큼 이동한 횟수를 의미하기 때문에 이 몫과 (digit + 1) 값을 더해주면 해당 자리 수에서의 어떤 수인지 구할 수 있습니다.
• 만약 해당 수가 n보다 크다면 이어붙인 수의 개수보다 더 큰 자리에 해당한다는 뜻이므로 -1을 출력합니다.
• 만약 그렇지 않다면 남은 k를 k에 해당하는 자리 수로 나눈 나머지를 구합니다. 이 나머지는 위에서 구한 k가 들어가는 해당 자리 수에서 몇 번째 수인지 의미하게 됩니다.
• 이 나머지를 이용하여 k에 해당하는 수가 어떤 수인지 찾습니다.