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

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

 

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

---

1.  아이디어

 

N의 크기에 비하면 메모리 크기가 작아서 진짜 수를 문자열로 이어 쓰는 방식으로는 해결할 수 없다.(아마)
출력할 K번째 자리수가 실제로 어떤 수에 포함되어있는지를 구하는 방식으로 해결했다.

---

2. 문제풀이

 

1부터 9까지는 1자리, 10부터 99까지는 2자리 이렇게 수가 커지면 자리수도 점차 커지며 커지는 순간은 10의 거듭제곱이 되는 순간이다.
이를 활용해 현재 수와 현재 수의 자리수를 가지고 K에서 현재 수의 자리수를 빼는 과정을 반복해서 더 빼면 K가 음수가 되기 전까지 반복한다. 그러면 현재 수에서 K번째 위치의 수를 구해서 정답을 알아낼 수 있다.

---

3. 코드

 

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());
        int K = Integer.parseInt(st.nextToken());

        int num = 0;  // 현재 수
        int len = 1;  // 현재 수의 길이
        int flag = 10;  // 현재 수가 10의 거듭제곱인지 판단하는 flag 변수

        while (K - len >= 0) {
            K -= len;
            num++;

            if (num == flag) {
                len++;
                flag *= 10;
            }
        }

        // 현재 수가 N보다 크면 불가능한 상황
        if (num > N) System.out.println(-1);
        else System.out.println(String.valueOf(num).charAt(K));
    }
}

---

4. 후기