1790번 수 이어 쓰기 2

수 이어 쓰기 2 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	64 MB	1882	491	389	31.070%

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤100,000,000)과,  k(1≤k≤1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다.

출력

첫째 줄에 앞에서 k번째 자리 숫자를 출력한다. 수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우는 -1을 출력한다.

예제 입력 1 

20 23

예제 출력 1 

6

출처

• 문제를 만든 사람: author5

알고리즘 분류

• 구현

이 문제는 브루트 포스로 절대 풀수없는 문제이다 왜냐면 10억번째 숫자가 뭔지를 알아내야 하기 때문이다. 1억번을 훨씬 초과 하기 때문에 절대 시간내에 풀 수없다. 그렇다면 중간 중간 많은 숫자들을 건너 뛸 수 있는 방법을 생각 해 내야 한다.

우선 자리 수 별로 숫자가 몇개 씩 있는지 살펴보자.

한자리수 : 1 ~ 9  , 9개 * 1 = 9개

두자리수 : 10~ 99, 90개 * 2 = 180개

세자리수 : 100~999, 900개 * 3 = 2700개

...

이런식으로 각 자리수마다 몇개의 숫자가 있는지를 알아낼수 있다.

그렇다면 k번째 가 어떤 숫자인지를 알아낼 수 있다.

1~ 10 ~ 100 ~ 1000 ~~~

에서 각 자리수에서 첫번째 나오는 1의 번호를 붙여보면 다음과 같다.

1번, 1+9 = 10번 , 10 + 90*2 = 190번, 190+ 90*3 = 2890번 ...

before라는 화살표로 앞의 1번을 가리키게하고 after라는 화살표로 뒤의 1번을 가리키게 한다. 그러면서 before와 after를 계속 옮겨가면서 조사하는것이다.

예를들어 맨 처음 반복에서는 before는 첫번째 1을 가리키고 after는 두번째 1(190번)을 가리킨다. 그다음 반복에서는 before는 두번째 1(190번)을 after는 세번째 1(2890번)을 가리키는것이다.

그리고 반복을 해 나가면서 k번째 수(23)가 before와 after사이에 있는지를 조사한다.

문제 예시 20 23 을가지고 예를 들어보자. 이상황에 K는 23이다. 즉, 1~20까지 차례대로 썻을때 23번째 숫자가 뭐냐를 물어보는거다.

before 1 after 10 -> k가 after보다 크므로 계속 진행

before 10 after 190 -> 10 < k < 190 이므로 k번째 수는 이 before 와 after 사이에 있다.

before가 가리키는 숫자는 10 중에서 앞의 1부분이다.

23(k)에서 10을 빼고 = 13

이 13을 자리수(2)로 나눈다.  = 6

이 13을 자리수2로 모듈러 연산 한다 = 1

그렇다면 이 수는 10 + 6 = 16이며

가리키는 숫자는 16중에서 6을 나타낸다. 왜냐면 모듈러 연산 값이 1이기 때문이다. 만약 모듈러 연산 값이 0이었다면 맨앞 숫자를 나타냈을 것이다.(1)

이런 방식으로 알고리즘이 동작한다.

이런방식으로 동작이 가능한 이유는 우선 k가 있는 범위를 매우 빠르게 줄일 수 있다.(before와 after를 활용해서)

그다음, before번째 숫자는 무조건 1, 10, 100, 1000 ... 에 나오는 숫자들 중 하나의 맨 앞부분인 1일것이다.

그렇기 때문에 before번째에서 추가로 몇번을 더 가야 k번째 숫자가 나오는지 알 수 있는것이다. 그것이 k - before이다.(앞으로 더 나아가야할 횟수)

위 예제에서 k-before = 23 - 10 = 13이다. 즉, 10에서 13번의 숫자를 더 거쳐가면 k번째 숫자를 구할수 있다는 것이다. 

현재 자리수는 2자리수이다. 따라서, 2개의 숫자를 지나갈때마다 십진수 하나씩 올라간다. 10 11 12 ...

그래서 나누기 연산을 통해 10에서 몇이 더해져야 하는지 구하는것이고, 모듈러 연산을 통해 그값의 십진수중에서 어떤 숫자인지를 골라내는것이다.

글로 설명할라니까 굉장히 어려운거 같다..

수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우는 -1을 출력한다.

이 조건을 마지막으로 만족 시켜야 하는데, 예를 들어 N이 11인 경우 K는 13까지만 가능하다. 14부터는 무조건 -1을 출력해야 한다.

위의 알고리즘 대로 돌리면 우리는 k번째 숫자가 포함된 십진수가 어떤 십진수인지를 알아낼수 있다고 했다.

예를들어 10에서 6을 더해서 16을 만들고 16에서 0번째숫자 1과 1번째숫자 6중에서 1번쨰 숫자인 6을 선택함으로써 알고리즘을 종료한것처럼.

이떄 16이라는 십진수를 알아낼수 있다.

이 16이 N보다 크다면 그 숫자는 원래 만들어낼수 없는 숫자였다는 의미이다. 그렇기 때문에 이런 상황에서 -1을 출력해야 한다.

#include <iostream>
#include <deque>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
 
int main() {
    int n, k;
    cin >> n >> k;
 
    long long before = 1;
    long long after = 10;
    int i = 1;
    while (true) {
        if (before <= k && k < after) {
            int dist = k - before;
            int plus = dist / i;
            int remain = dist % i;
            int start = pow(10, i - 1);
            start += plus;
            if (start > n) {
                cout << -1 << endl;
                return 0;
            }
            deque<int> deq;
            while (start != 0) {
                int remain = start % 10;
                start /= 10;
                deq.push_front(remain);
            }
            cout << deq[remain] << endl;
            break;
        }
        before = after;
        after += (i + 1) * 9 * pow(10, i);
        i++;
    }
 
    return 0;
}