[C++/1790] 수 이어 쓰기 2

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

일단 입력값을 보자마자 일반적인 방식으로 풀 수 없다고 생각했다.

N의 크기 (1 <= N <= 100,000,000)과 K (1 <= K<= 1,000,000,000)이 주어진다. N은 1억이고 K는 10억이다. 일반적으로 10억번째의 배열을 생각할 수 있을까? 10억개를 담을 수 있는 것이 있을까? 일반적으로는 말이 되지 않는다. 그래서 생각을 여러번 거쳤다.

일단 12345678910111213141516...9991000 이런식으로 문자열을 생성할 수 있어야한다. 그래서 천천히 생각을 해보았다. 흠 여러여러 돌아다니다가 결국엔 이렇게 해결할 수 밖에 없지 않을까 생각했다.

1개의 자리수 (1 ~9)
2개의 자리수 (10~99)
3개의 자리수 (100~999)
4개의 자리수 (1,000~9,999)
5개의 자리수 (10,000~99,999)
6개의 자리수 (100,000~999,999)
7개의 자리수 (1,000,000~9,999,999)
8개의 자리수(10,000,000~99,999,999)
9개의 자리수(100,000,000)

이렇게 구할수 밖에 없겠다 생각을 했다. 만약 n의 값이 주어졌다면? 그 자리수 만큼 길이를 구해주는 것이다. 이런식으로 진행을 해보자. 예를 들어 입력으로 주어진 것은 n이 20이다. 즉 20까지 이어서 문자열을 만들어야하는데 그 길이가 얼마가 될까?

1~9까지의 길이는 (9 - 1) + 1 = 9이다. 1자리 수이기 때문에 * 1 을 해준다. 그렇다면 총 길이는 9

10~99 까지의 길이는 (99 - 10) + 1  = 90이고, 2자리 수이기 때문에 * 2를 해준다. 그렇다면 총 길이는 9 + 180 = 189

이런식으로 값을 구하면 될 것이다. 그래서 그 길이를 구할 수 있는 코드는 이러하다.

일단 마지막 숫자를 구해야한다. 그래서 그 숫자의 end는 시작하는 값 * 10 - 1 은 마지막 값이 된다. 하지만 그 마지막 값이 우리가 원하는 숫자보다 크다면? end는 우리가 원하는 숫자가 되고, 그 숫자에서 방금 위에 작성한 공식을 적용하면 된다.

그래서 나온 공식은 ((마지막 숫자 - 그 자리수의 첫번째 숫자) + 1 ) * 자리수 가 될 것이다.

그렇다면 우리는 이제 총 길이를 구하는 코드를 작성했다는 것이다. 코드는 아래와 같다.

int getLength(int number) {
	
	int len = 0, n_len = 1;
	
	for(int i = 1; i <= number; i *= 10){
		
		int end = i * 10 - 1;
		if(end > number) end = number;
		
		len += ((end - i) + 1 ) * n_len;
		n_len++;
	}
	
	return len;
}

 

이제 길이는 구했는데, 과연 그게 몇번째인지는 어떻게 구할 수 있을까? 일단 그 숫자까지 쭉 나열해서 값을 구했고 그런 다음에 23번째를 찾으면 될까? 라는 생각을 했다. 하지만? k의 범위가 10억까지니까 일단 10억까지 나온다는 것 아닐까? 그렇다면 만약에 10억번째를 찾으라고 한다면? 그것을 구할 수 있을까? 절대 없을 것 같다. 그래서 이제는 과연 우리가 원하는 k번째 위치는 어떻게 구할 수 있을까?

우리는 일단 n번까지 총 길이를 구할 수 있었다. 그렇다면? 이때 우리가 원하는 k번째의 위치를 빠르게 찾을 수 있는 방법으로 이분탐색을 생각해볼 수 있겠다. 그렇다면 log (문자열의 길이)이기 때문에 문제를 시간내로 해결할 수 있을 것이다.

그렇다면 start와 end 값을 어떻게 결정해야할까? k의 값이 23이라면? 23번째를 구하는 것이니까 23번째가 될 수 있는 1부터 n까지 중에 절반씩 잘라가면서 중간값이 우리가 원하는 k의 값인 23보다 작다면? start를 늘려나가고, k가 23보다 크다면? end를 줄여나가는 방식을 취해서, 방금 만든 getLength함수를 사용해 길이를 구해서 문제를 해결할 수 있을 것이다.

그래서 아래의 이분 탐색으로 우리는 그것을 구할 수 있다. 어떤 숫자인지를 찾을 수 있다.

int answer = 0;
while(start <= end) {

    int mid = (start + end) / 2;
    int length = getLength(mid);

    if(length < k){
        start = mid + 1;
    } else{
        answer = mid;
        end = mid - 1;
    }

}

그렇다면 이제 마지막이다. 우리는 그 숫자를 찾았으니 그 숫자의 몇번째가 k일까?

여기서 엄청난 위기가 찾아왔다. 모르겠다는 것이다. 어떻게 구할 수 있을까? 일단 우리가 구한것은 이러하다.

1. 그 해당 위치에 있는 숫자

이것을 위해서 여기까지 온 것이다. 그렇다면 그 숫자까지 오는 중에 하나가 뭐가 될거 아니야?

어쨌든 여기까지 오면서 그 해당 위치에 있는 숫자가 16이다. 여기까지의 길이가 무엇일까?

12345678910111213141516 즉 6이 나와줘야 한다는 것이다. 그렇다면 어떤 공식이 필요할까? 

아주아주 한참한참 고민을 했는데, 일단 16이라는 값을 string으로 만들어보자.

'16'인데 그렇다면 이 값은 [1][6] 인데, 마지막을 가리키고 있으면서 ' 12345678910111213141516'의 길이에서 k번째 만큼 자른다면? 그 위치가 되지 않을까? 라는 생각을 겁나했지만?

전체 길이에서 몇번째까지 가야할지는 알고 있지? 전체 길이 - k번재 만큼 자르면? 그게 그 위치가 될 것이고?

그렇다면 정답이 될 것이다. 에서 바로 틀려버렸다. str[총길이 - k번째] 어라라? 그러면 0번째가 되는구나? 1이 나와야하는데 그렇다면 맨 뒤에서 부터 체크를 해주면 되지 않을까?

str[str.size() - 1 - (총길이 - k)] 이런식으로 한다면? 정답이다. 왜인지는 아직도 모른다.. 그냥 두가지를 한번 써봤다.

#include<iostream>
#include<string>

using namespace std;

int n,k;

void init() {
	cin >> n >> k;
}

int getLength(int number) {
	
	int len = 0, n_len = 1;
	
	for(int i = 1; i <= number; i *= 10){
		
		int end = i * 10 - 1;
		if(end > number) end = number;
		
		len += ((end - i) + 1 ) * n_len;
		n_len++;
	}
	
	return len;
}

void solve(int start, int end) {
	
	int answer = 0;
	while(start <= end) {
		
		int mid = (start + end) / 2;
		int length = getLength(mid);
		
		if(length < k){
			start = mid + 1;
		} else{
			answer = mid;
			end = mid - 1;
		}
		
	}
	
	int c = getLength(answer);
	string str = to_string(answer);
	cout << str[str.size() - 1 - (c - k)];
	
	return;
	
}

int main() {
	
	init();
	if(getLength(n) < k){
		cout << -1;
		return 0;
	}
	
	solve(1, n);
	
	return 0;
}