[백준 01790] 수 이어 쓰기 2 [Java]

문제

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

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

입력

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

출력

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

1790번: 수 이어 쓰기 2

---

풀이

주어진 1부터 N의 수를 나열했을 때 K번째 자리에 위치한 숫자를 출력하는 문제다.

모든 수를 한 자리씩 탐색하는 방법은 당연히 시간초과가 발생한다.

 

구간의 자릿수를 제외하는 방식으로 풀이했다.

1 ~ 9 = 9

10 ~ 99 = 90 * 2

100 ~ 999 = 900 * 3

으로 자릿수( digit )가 증가할 때마다 자릿수로 만들 수 있는 최대 숫자까지의 순서는 9 * 10^(digit - 1) * diigt의 누적합이 된다.

K번째 자리에 위치한 수를 출력해야 하므로 K를 넘지않는 선에서 생략 가능한 자릿수를 제외하자.

이제 남은 K는 10^digit 보다 작은값이 된다.

정답을 계산하기에 앞서 인덱스는 0부터 시작하므로 K를 1빼주자.

처음에 주어진 K번째에 위치한 수를 구하기 위해서는 

지금까지 생략한 digit만큼의 위치와, 남은 K를 다음 digit으로 나눈 값만큼 더한 값이다.

 만약 num이 N보다 크다면, K번째 자릿수는 없다. -1을 출력하고 아닌 경우에만 정답을 출력하자.

다음 자릿수 digit로 나눈 나머지 값이 K번째 자릿수가 된다.

---

소스코드

보기