[백준] 1790번 : 수 이어 쓰기 2 – JAVA [자바]

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

1790번: 수 이어 쓰기 2

 

 

---

• 문제

 

 

---

• 문제 풀이

백준 1790번 수 이어 쓰기 2는 골드 5 난이도의 수학 및 구현 문제이다. 

 

이 문제에서는 정수 N과 K가 주어진다. 그리고 1부터 N까지 수를 이어서 썼을 때 K 번째 자리 숫자가 어떤 숫자인지 구하면 된다.

 

이 문제를 풀 때 모든 수를 연결해서 풀면 시간 초과나 메모리 초과가 뜨기 때문에 좋은 방법은 아니다. 

 

아래와 같이 자릿수가 증가하면서 숫자의 개수가 변하는 규칙을 알 수 있다.

 

자릿수	숫자 갯수	자리 갯수
1	9개 (1 ~ 9)	9개 (1 * 9)
2	90개 (10 ~ 99)	180개 (2 * 90)
3	900개 (100 ~ 999)	2700개 (3 * 900)
4	9000개 (1000 ~ 9999)	36000개 (4 * 9000)

 

이 표를 이용해서 문제에서 주어진 예시를 보겠다. 문제에서 주어진 K는 23이다. 

 

즉, K = 23, 1 * 9 = 9개 이므로, 자릿수가 1인 경우는 생략 가능하다.

 

그럼 K번째 수는 자릿수가 2인 숫자에 속해 있다는 사실을 알 수 있다.

 

23 - 9는 14 이므로, (14 - 1) / 2 (자릿수)의 몫은 6 (건너뛸 숫자의 개수), 나머지는 1인 것을 알 수 있다.

 

따라서 자릿수가 2인 숫자의 시작인 10부터 15까지, 6개의 숫자를 건너뛰고 16에서 인덱스 1인 글자가 정답이다. 즉, 6이 정답이다. 여기서 (14 - 1)을 해주는 이유는 K를 0부터 시작하기 위해서이다. 

 

문제에서 주어진 조건을 살펴보겠다. 문제에서는 다음과 같은 조건이 주어졌다. "수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우는 -1을 출력한다."

 

위의 방식대로 하면 어떤 숫자에서 어떤 인덱스를 구해야 하는지 알 수 있다. 예를 들어서, 위에 예제에서 16 같은 경우이다. 만약에 이 숫자가 N보다 작으면 K번째 자리 숫자가 없는 경우가 되기 때문에 -1을 출력하면 된다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

 

 

---

• 코드

 

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()); // n 입력
        long k = Long.parseLong(st.nextToken()); // k 입력

        long numLen = 1; // 찾고자 하는 숫자의 자리수
        long numCount = 9; // 찾고자 하는 숫자의 자리수별 개수 (1자리 숫자: 9개, 2자리 숫자: 90개, ...)
        while (k > numCount * numLen) { // k가 현재 자리수별 최대 개수를 초과하는 경우
            k -= (numLen * numCount); // k에서 현재 자리수별 최대 개수를 뺌
            numLen++; // 자리수를 증가시킴
            numCount *= 10; // 최대 개수를 업데이트
        }
        k -= 1; // k를 0부터 시작하도록 조정

        long num = (long)Math.pow(10, (numLen - 1)) + (k / numLen); // 찾고자 하는 숫자 계산
        if (num > n) { // 찾고자 하는 숫자가 n보다 큰 경우
            System.out.println(-1); // -1 출력 (해당 숫자는 없음)
        } else {
            System.out.println(String.valueOf(num).charAt((int)(k % numLen))); // 찾은 숫자의 k번째 자리 출력
        }
    }
}