백준 1790 - 수 이어 쓰기 2 JAVA

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

 

처음에 딱히 방법이 생각이 나지 않아서

N번째 자리까지 수를 계속 추가하고 k번째를 출력하는 것으로 하였다.

역시나 N의 범위 때문에 메모리 초과가 된다.

 

 

import java.util.Scanner;

public class 백준_수이어쓰기2_1790 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int k = sc.nextInt();

		long tmp = k;
		long finalNum = 0;
		long numlength = 1;
		long numCnt = 9;

		while (tmp > numlength * numCnt) {
			tmp -= (numlength * numCnt);
			finalNum += numCnt;
			
			numlength++;
			numCnt *=10;
		}
		
		
		finalNum = (finalNum+1)+ (tmp-1)/numlength;
		if(finalNum > N) {
			System.out.println(-1);
		}else {
			int index = (int) ((tmp-1)%numlength);
			System.out.println(String.valueOf(finalNum).charAt(index));
		}
	}

}

 

1. 입력값을 N, k를 받아온다.

 

2.  - tmp에 k 복사

    - finalNum = k번째 숫자를 포함하고 있는 순차적으로 싸인 순서 숫자

      ex) 14 15 16으로 저장될 때 k번째 숫자가 5라면 finalNum은 15

1의자리 numLength = 1	1~9	9개 numCnt = 9
10의 자리  numLength = 2	10~99	90개 numCnt = 90
100의 자리 numLength = 3	100~999	900개 numCnt = 900

 

3. K번째에서 가장 가까운 근사치를 가기 위해 while반복

   - 기본적인 자릿수를 finalNum에 저장

   - tmp에서 자릿수를 빼고 남은 값

 

4.  ((tmp-1)/numlength)의 몫 + (finalNum + 1) 은 순차적으로 싸인 숫자

    ((tmp-1)/numlength)의 나머지는 숫자에서의 index의미

 

 

 

 

생각해내기가 어려웠다. 짜증 난다. 짜증 내지 말자