백준 1790 수 이어 쓰기 2 (C++)

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

#include <iostream>
#include <vector>


using namespace std;




int calLen(int n){

    int len = 0;

    for (int start = 1, i = 1; start <= n; start *= 10, i++) {
        int end = start * 10 - 1;
        if (end > n) {
            end = n;
        }
        len += (end - start + 1) * i;
    }
    return len;

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;
    cin >> n >> k;

    if (calLen(n) < k) {
        cout << -1;
        return 0;
    }

    int pos;
    int s = 1;
    int e = n;

    while (s <= e) {
        int mid = (s + e) / 2;
        int len = calLen(mid);

        if (len < k) {
            s = mid + 1;
        } else {
            pos = mid;
            e = mid - 1;
        }
    }


    int cur = calLen(pos);
    string str = to_string(pos);
    cout << str[str.size() - 1 - (cur - k)];

    



    return 0;
}

1. 문제

n, k가 주어진다. 1부터 n까지 쭉 나열하여 수를 만들었을 때(12345678910111213...) k번째 숫자를 구하라.

2. 풀이

이 문제는 다음의 순서로 풀 수 있다.

1. k번째 자리가 속할 수 있는 숫자를 찾는다.
2. 해당 숫자에서 k번째 자리가 그 숫자의 몇 번째인지 계산하여 출력한다.

int calLen(int n){

    int len = 0;

    for (int start = 1, i = 1; start <= n; start *= 10, i++) {
        int end = start * 10 - 1;
        if (end > n) {
            end = n;
        }
        len += (end - start + 1) * i;
    }
    return len;

}

n이 주어지면 1부터 n까지 이어붙였을때 몇 자리가 나오는 지 계산하는 함수이다. 

• 1-9: (9-1+1)*1
• 10-99: (99-10+1)*2
• 100-999: (999-100+1)*3

즉, 해당 범위 내 숫자의 개수*자릿수로 구할 수 있다. 

    int n, k;
    cin >> n >> k;

    if (calLen(n) < k) {
        cout << -1;
        return 0;
    }

n과 k를 입력받는다. 1부터 n까지 이어붙인 길이보다 k가 더 크다면 숫자를 표현할 수 없으므로 -1을 출력하고 프로그램을 종료한다.

    int pos;
    int s = 1;
    int e = n;

    while (s <= e) {
        int mid = (s + e) / 2;
        int len = calLen(mid);

        if (len < k) {
            s = mid + 1;
        } else {
            pos = mid;
            e = mid - 1;
        }
    }

k가 속한 숫자가 몇인지 이분탐색을 통해 구한다. 만약 1부터 mid까지의 길이보다 k가 크다면, k가 속한 숫자가 오른쪽에 있다는 의미이므로 우측 범위에서 탐색한다. 그렇지 않다면 왼쪽 범위를 탐색하여 숫자를 더 줄일 수 있는지 확인한다.

    int cur = calLen(pos);
    string str = to_string(pos);
    cout << str[str.size() - 1 - (cur - k)];

 위에서 숫자 pos를 구했다면 1부터 pos까지 이어붙인 길이를 구한다. 1부터 pos라는 수의 끝까지 이어붙였으므로 전체 길이에서 k를 뺀 값을 str에 맞춰 계산하여 출력하면 정답을 구할 수 있다.