[백준] 1790번 수 이어 쓰기 2 Java

문제 링크

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

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다.

출력

첫째 줄에 앞에서 k번째 자리 숫자를 출력한다. 수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우는 -1을 출력한다.

알고리즘: 수학, 구현

풀이

길이가 1인 수부터 차례대로 체크한다.
길이가 1인 수의 길이 합은 9이다. 이 값이 K보다 크거나 같다면 K번째 수는 길이가 1인 수이다. 그러면 bn + K/l(길이)가 K번째가 속한 수이고 그 수의 K%l번째가 K번째이다. 나머지가 없는 경우는 그 수의 마지막 번째 수가 K번째임. (여기서 bn은 초기값이 0임)

만약에 K보다 작다면 길이가 2인 수를 봐야 한다. 길이가 2인 수를 체크하기 전에 bn은 길이가 1인 값중 제일 큰 값을 대입해준다. K에는 길이가 1 인수의 길이 합인 9를 빼준다. 그리고 위와 같은 방법을 K보다 크거나 같을 때까지 반복해준다.

소스 코드

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

public class Main {
    static int w = 1;
    static long K;
    static int N;
    static long boundary = 9;
    static long ans_num = 0;
    static long temp = 9;
    static char ans;
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      K = Long.parseLong(st.nextToken());
      while(true) {
          if(ans_num > 100000000) break;
          
          if(boundary < K) {
              K = K - boundary;
              ans_num = temp;
              w += 1;
              update_boundary();
          } else {
              long Q = K/w; //몫
              int R = (int) K%w; //나머지
              if(R != 0) {
                  ans_num += Q + 1;
                  String str_n = Long.toString(ans_num);
                  ans = str_n.charAt(R-1);
              } else {
                  ans_num += Q;
                  String str_n = Long.toString(ans_num);
                  ans = str_n.charAt(str_n.length() - 1);
              }
              break;
          }
      }
      if(N < ans_num) System.out.println(-1);
      else System.out.println(ans);
    }
    
    static void update_boundary() {
        StringBuilder sb = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for(int i=0; i<w; i++) {
            sb.append('9');
            if(i==0) sb2.append('1');
            else sb2.append('0');
        }
        temp = Long.parseLong(sb.toString());
        boundary = w * (temp - Long.parseLong(sb2.toString()) + 1);
    }
}