[자바] 백준 1790 - 수 이어 쓰기 2 (java)

목차

문제 : boj1790

 

 

필요 알고리즘

• 구현, 수학
  
  • 수학적 사고를 통해 구현할 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  N이 1억까지이므로, 언어에 따라 실제로 수를 이어봐서 풀 수도 있어 보인다. 실제로 파이썬은 이렇게 풀 수 있음을 확인했다. 자바는 안될 것 같다.

 

  우선 N이 100,000,000인 경우는 제외하고 최대 8자리까지 가능하다고 생각해보자. 그렇다면 자리수가 i개인 숫자는 ix9x10^(i-1) 개 만큼의 자리수를 차지함을 알 수 있다. 예를들어 2자리수인 10, 11, 12, ..., 99가 차지하는 자리수는 2x9x10^1 = 180개 이다.

 

  그렇다면 저 자리수들을 계속 더해나가다가 k를 넘는순간으로, k번째 자리수에 해당하는 숫자가 몇자리 숫자인지 알 수 있다. 예를들어 현재까지 i에 따라 더해진 자리수가 sum이라 할 때, k가 23인 경우 i=1에서 sum=9, i=2에서 sum=189이고, k(23)는 9와 189 사이이므로 2자리숫자임을 알 수 있다. 그렇다면 10^(i-1)+(k-[i-1까지의 sum]-1)/i 가 k번째 자리수를 포함하는 숫자가 된다. 예를들어 k=23인 경우 10+(23-9-1)/2 = 16 이므로 k번째 자리수에 해당하는 숫자는 16이고, k번째 자리수는 '1'또는 '6' 중 하나가 될 것이다. k = 200이라면 i=3이 되고, 10^(i-1)+(k-[i-1까지의 sum]-1)/i  = 100 + (200-189-1)/3 = 103 이고, k번째 수는 '1', '0', '3' 중에 하나가 될 것이다. 만약 이렇게 구한 숫자(103)가 N보다 클 경우 -1을 출력하고 종료해주면 된다.

 

  k=200이었고, 그럼 해당하는 숫자는 103이다. 이 중 몇 번 인덱스의 수가 k번째 자리수인지는 (k-[i-1까지의 sum]-1)%i 로 알 수 있다. 해당값은 1 이므로, '0'이 답이 된다.

 

  마지막으로 제외해두었던 N이 100,000,000 인 경우만 마지막에 예외처리해줘서 풀었다. k-sum이 9 이하라면 '100,000,000'의 9자리 중 하나인 경우이다.

k-sum<=9 ? (k-sum==0?1:0) : -1

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int sum = 0;
        int base = 1;
        for (int i = 1; i <= 8; i++, base*=10) {
            int cnt = base*9;
            if (sum + cnt*i < k) {
                sum += cnt*i;
                continue;
            }

            int num = base + (k-sum-1)/i;
            if (num > n) System.out.println(-1);
            else System.out.println(String.valueOf(num).charAt((k-sum-1)%i));
            return;
        }

        System.out.println(k-sum<=9 ? (k-sum==0?1:0) : -1);
    }
}