[BOJ] 1790 수 이어 쓰기 2 JAVA

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

1790번: 수 이어 쓰기 2

 

메모리 : 12868 kb

실행시간 : 112 ms

 

문제분석

문제대로 수를 쭉 나열해서 인덱스를 뽑아오면 메모리초과, 시간초과가 날 것이 분명한 문제 ..
규칙을 찾아야 한다

 

걸린시간

2시간 ⏱️

 

풀이방법

1 자리 : 1 ~ 9 (1 - 9개) + 9개
2 자리 : 10 ~ 99 (10 - 189개) + 180개
3 자리 : 100 ~ 999 (190 - 2889개) + 2700개
4 자리 : 1000 ~ 9999 (2900 - 38889개) + 3600개

위 규칙을 활용해서

1. k가 포함된 자리 수를 찾은 뒤
	- 자리 수마다 9 * i * Math.pow(10, i - 1) 개씩 늘어난다는 점을 활용해 k의 자리 수 구하기
2. 몫과 나머지를 이용해 k가 위치하는 수와
	- k에서 이전 자리 수 개수만큼 빼준다. (k가 3자리 수라면 k - 189)
	- k가 포함된 수를 구한다 ((k - 1)/ 자리 수) + Math.pow(10, (자리 수 - 1)) // k에서 1을 빼주고 자리 수
		로 나눠줘야 함
	- 만약 이 수가 N보다 클 경우 -1 출력
3. 실제 k번째 수를 찾아가는 과정이 필요하다
	- k번째 수 계산을 위해서는 해당 자리 수 첫 번째 부터 떨어진 거리를 알아야 하기 때문에 k-1 해준다 (3자리 수는 190부터 시작인데 2번에서 189를 빼줬기 때문에 -1 더 해주는 것)
	- k가 포함된 수에서 k를 i로 나눈 나머지 위치의 수를 뽑아낸다.

 

포인트

규칙찾기 🧩

 

코드

/*
1 자리 : 1 ~ 9 		(1 - 9개) + 9개
2 자리 : 10 ~ 99 		(10 - 189개) + 180개
3 자리 : 100 ~ 999		(190 - 2889개) + 2700개
4 자리 : 1000 ~ 9999	(2900 - 38889개) + 3600개
*/
package study.day0811;

import java.io.IOException;
import java.util.Scanner;

public class BOJ_1790_수이어쓰기2 {	// 메모리 : 12868kb	실행시간 : 112ms
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextInt();
		long k = sc.nextInt();
		long i = 2;
		long endPrev = 9;

		if(k < 10) {	// 만약 k가 1자리 수라면
			if(k <= N) System.out.println(k);	// k가 범위내에 있을 경우 k출력
			else System.out.println(-1);	// 범위 밖이면 -1 출력
			return;
		}
		while(true) {	// N이 몇 자리 수인지 파악하기
			endPrev += 9 * i * Math.pow(10, i - 1);
			if(k <= endPrev) {				
				endPrev -= 9 * i * Math.pow(10, i - 1);
				break;
			}
			i++;
		}

		k -= endPrev;
		long nowNum = (int) (((k - 1)/ i) + Math.pow(10, (i - 1)));	// k가 포함된 수 구하기
		k--;	// 자리수 계산을 위해서는 i자리 수 첫번 째 부터의 거리를 알아야 하기 때문에 -1 해준다

		if(nowNum > N) System.out.println(-1);	// k가 포함된 수가 N보다 크면 -1 출력
		else {
			System.out.println(String.valueOf(nowNum).charAt((int) (k % i)));	// k % i 번째 인덱스 출력
		}

	}
}