BOJ) 수 이어 쓰기 2

수 이어 쓰기 2

1790번: 수 이어 쓰기 2

풀이

 

 주어지는 n과 k의 범위가 각각 1억, 10억이어서 아무 생각없이 int 형으로 생각하고 문제를 풀어나가서 틀린 부분을 찾는데 시간이 조금 걸렸다. 왜냐하면, 입력 숫자가 1억인 경우에, 누적으로 문자열 길이를 저장하는 함수가 9억 9천만(....)*9 까지 더해주기 때문이었다. 

 

일단, 숫자를 문자열에 그대로 붙였을 때, 1~9는 한 글자가 증가하고 10~99는 두 글자가 증가한다. 100~999는 세 글자가 증가하는데, 위의 규칙을 살펴보면 10^(n-1) ~ (10^n) -1 개의 숫자가 n만큼 문자열에 추가 됨을 있음을 알 수 있다.

그래서 처음에는 Math.pow를 이용해서 직접 구해줬었는데, 코드 실패가 뜨고 다시 천천히 보니까 증가에 규칙이 있음을 알 수 있었다.

 

숫자 범위	숫자 갯수	숫자 길이
1~9	9	1
10~99	90	2
100~999	900	3
1000~9999	9000	4
10000~99999	90000	5
100000~999999	900000	6
1000000~9999999	9000000	7
10000000~99999999	90000000	8

위의 표를 살펴보면 숫자의 갯수는 다음 범위로 증가할 때마다  *10 이 되고있고, 길이는 +1이 되고있다.

그래서 Math.pow를 두 번 호출하고 -연산을 해서 숫자의 갯수를 구하는 것 보다는 *10을 해주는 것이 효율적이라고 판단해서 고쳤다.

 

먼저, 문제의 조건에 따라서 k가 호출할 수 있는 범위를 넘어가면 -1을 리턴하게끔 설정했다.

(사실 풀고나서 느낀건데, 이 부분도 필요없다고 생각한다..)

 

호출할 수 있는 경우에, answer의 값을 바꿀 수 있도록 로직을 짰다.

K가 숫자의 범위 중 어디에 있는지 먼저 파악했다.

파악된 숫자 범위 이전까지 문자열 갯수를 K에서 빼준 다음, 숫자 범위에서 몇 번째에 해당하는 문자를 구해야하는지 구해주었다.

 

문제에 제시된 예시처럼 n=20 k=23인 경우로 코드를 진행시켜보면,

sum이 현재 돌고있는 길이의 갯수를 다 포함할 수 있는지 체크해주었다. => sum+(숫자 갯수*숫자 길이) >= K 인 경우

만약 모두 체크할 수 없다면, 구해야하는 문자열의 숫자는 (숫자 길이)에 해당하는 숫자이다.

여기서 숫자 길이는 3자리 수인지, 4자리 수인지를 말한다. (100, 1000 은 숫자 길이가 3, 4가 된다)

 

남은 k는 숫자 길이가 1까지만 탐색할 수 있었으므로 k-sum = k-9가 된다.

따라서, k에는 14라는 숫자가 남아있다.

숫자 길이가 2인 (10 ~ 99 사이)의 숫자에서 14번째 숫자를 구해야 하는 것이다.

 

10 11 12 13 14 15 16 ...

14번째 숫자는 16에 해당하고, 1과 6중에 뒤에 해당하는 6임을 알 수 있다.

 

이에 따라, 10 + (14/2) -1 을 통해 어떤 숫자가 나오는지 알 수 있다.

이때, 만약 남은 k가 14가 아니고 13일 때도 16이라는 숫자가 나와야한다.

그래서 k%(숫자 len)이 딱 맞아 떨어지는 경우가 아니라면, k/숫자len 에 +1을 해줘야 함을 도출할 수 있다.

 

숫자를 구한 이후에는 String에서 문자열의 위치를 구해주었다.

k%len이 0이 나오는 경우는, 구해진 숫자의 마지막 인덱스를 가리키고, 1~len-1 까지는 문자열의 맨 앞부터 숫차적으로 가리킨다.

 

이에 따라 조건 문을 걸어서 charAt을 통해 숫자를 구해주었다. 이 때, 값은 Ascii code에 따라 48+n 이 되므로, charAt을 통해 구한 코드 값에 -48을 해주어 답을 구했다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class NumberConnection_1790 {
    final static int MAX = 9;

    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());
        int k = Integer.parseInt(st.nextToken());

        System.out.println(solution(n,k));

        br.close();
    }

    private static int solution(int n, int k) {
        int answer = -1;

        if(getMaxLen(n) >= k) {
            int len =1;
            int cnt =9;
            int sum = 0;
            for(int i=1; i<=MAX; i++) {
                long tmp = (long)cnt*len;
                if(sum+tmp >=k) {
                    break;
                }
                len++;
                cnt*=10;
                sum+=tmp;
            }
            k -=sum;
            answer = (int) (Math.pow(10,len-1) + k/len -1);
            int order = k%len;
            if(k%len !=0) {
                answer++;
                answer = String.valueOf(answer).charAt(order-1)-48;
            } else {    // 0인 경우 마지막 인덱스 반환
                answer = String.valueOf(answer).charAt(len-1)-48;
            }
        }

        return answer;
    }

    private static int getMaxLen(int n) {
        int result =0;
        int cnt = 9;
        for(int i=1; i<=MAX; i++) {
            if(Math.pow(10,i) > n) {
                if(i !=1) {
                    result += (n-Math.pow(10,i-1)+1)*i;
                } else {
                    result = n;
                }
                break;
            } else {
                result += cnt * i;
                cnt *=10;
            }
        }
        return result;
    }
}