[백준] 1790번 수 이어 쓰기 2 (자바 풀이)

문제

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

1790번: 수 이어 쓰기 2

 

풀이

모든 수를 연결해서 풀면 시간초과 혹은 메모리 초과가 발생한다. 이 문제를 풀기 위해서는 다른 접근이 필요하다.

잘 생각해보면 아래와 같이 자릿수가 증가하면서 숫자의 갯수가 변하는 규칙을 알 수 있다. 

 

자릿수	숫자 갯수	글자 갯수
1	9개 (1~9)	9개
2	90개 (10~99)	180개
3	900개 (100~999)	2700개

 

이 규칙을 이용하면 몇번째 글자가 어떤 숫자에 포함되어 있는지 알 수 있다.

 

예를 들어 201번째 글자를 알고 싶다고 하자.

 

K=201, 1*9+2*90 = 189개 이므로, 자릿수가 2인 경우 까지는 생략 가능하다. 

 

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

 

이후 201-189 = 12이므로, (12-1)/3(자릿수) 은 몫은 3(건너뛸 숫자의 갯수), 나머지는 2인 것을 알 수 있다. 

 

따라서  자릿수가 3인 숫자의 시작인 100부터 101, 102, 3개의 숫자를 건너뛰고 103에서 2번째 글자가 정답이다.

 

여기서 헷갈리면 안되는게 103에서 0번째 글자=1, 1번째 글자=0, 2번쨰 글자=3 이다. 

 

따라서 답은 3이된다.

 

코드

import java.io.*;
import java.util.*;

public class Baekjoon_1790 {
	static int N,K;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		
		long target = 0;	// 찾을 숫자가 포함된 슷지
		long numLen = 1;	// 계속해서 올릴 자릿수
		long numCnt = 9;	// 9,90,900~
		
		while(K > numCnt*numLen) {
			K -= (numLen*numCnt);
			target += numCnt;
			
			numLen++;
			numCnt *=10;
		}
		
		target = (target+1) + (K-1)/numLen;	// 찾고자 하는 숫자가 포함된 숫자 
		
		if(target > N) {
			System.out.println(-1);
		}else {
			int idx = (int)((K-1)%numLen);
			System.out.println(String.valueOf(target).charAt(idx));
		}
	}
}

 

결과