백준 1790 수 이어 쓰기 2 (Java,자바)

jonghyukLee·2021년 12월 29일

이번에 풀어본 문제는
백준 1790번 수 이어 쓰기 2 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());

        long tmp_k = K;
        long len = 1;
        long num_cnt = 9;
        long res = 0;

        while(tmp_k > num_cnt * len)
        {
            tmp_k -= num_cnt * len;
            res += num_cnt;
            num_cnt *= 10;
            len++;
        }

        res = (res+1) + ((tmp_k-1) / len);

        if(res > N) System.out.print(-1);
        else
        {
            int idx = (int)((tmp_k-1) % len);
            System.out.print(String.valueOf(res).charAt(idx));
        }
    }
}

📝 풀이

N까지의 숫자를 쭉 이어붙인 후, K번째 숫자를 구하는 문제입니다.
입력범위가 굉장히 크기 때문에 숫자를 일일히 다 만들어서 체크하면 시간내에 해결해낼 수 없습니다.
먼저, 숫자를 이어붙였을 때
한자리 수 1~9는 1자리씩 9개,
두자리 수 10~99는 2자리씩 90개,
세자리 수 100~999는 3자리씩 900개가 이어 붙여진다는 규칙을 찾을 수 있습니다.
이 규칙을 활용하여 while문 내에서 주어진 K값이 어느 범위에 속하는지를 구하고, 남은 인덱스를 통해 K의 자리에 어떤 수가 들어있는지 확인해낼 수 있습니다.

반복문을 벗어난 시점에서 res는 현재까지 지나쳐온 자릿수의 위치를 지니고 있으며, tmp_k는 그 위치에서 더 가야하는 잔여 카운트값을 지니고 있습니다.
이후, res = (res+1) + ((tmp_k-1) / len) 에서는 K를 포함하고 있는 실제 숫자를 구하기 위해, 자릿수를 맞춰 res+1, 앞에서 한칸 이동했으니 tmp_k-1, 그리고 tmp_k-1을 len으로 나눈 몫은 해당 자릿수만큼 이동한 횟수를 의미하므로 두 값을 더해주면 실제 포함한 숫자를 구할 수 있습니다.
마지막으로, 조건에 맞게 N보다 작을경우 -1을 출력, 그렇지 않다면 나머지를 통해 res에서 idx번째 있는 숫자를 출력해주면 해결할 수 있습니다.