[백준] 수 이어 쓰기 2 1790번 (c++)

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

 

풀이 방법

1. 문제 접근:

단순히 1부터 시작하는 모든 수를 문자열로 이어 붙여서 k번째 문자를 찾는 방식은 시간 초과를 유발한다. 따라서 각 자릿수 별로 숫자가 몇 개나 등장하는지 계산하고, 이를 이용해 빠르게 k번째 문자가 어느 범위(몇 자릿수)에 속하는지 판단해야 한다.

2. 자릿수 범위별 숫자 개수:

• 한 자릿수: 1~9 ⇒ 총 9개

• 두 자릿수: 10~99 ⇒ 총 90개

• 세 자릿수: 100~999 ⇒ 총 900개

• …

일반적으로, d자리 수는 9 \times 10^{d-1}개 존재한다.

3. 자릿수 범위별 문자(숫자) 개수:

각 자릿수 범위 내 숫자가 N개라면, 문자열로 이어 붙일 때는 각 숫자가 d자리이므로 총 N \times d개의 문자가 생긴다.

예를 들어 두 자릿수(10~99)는 90개이고, 각 숫자는 2자리이므로 90 \times 2 = 180개의 문자가 생긴다.

4. k의 범위를 좁히는 과정:

1. 한 자릿수 문자열(9개)을 구성하는 문자는 9 * 1 = 9개.

2. k가 9보다 크면 k에서 9를 빼고, 다음 자릿수(두 자릿수)에 대해 같은 과정을 반복한다.

3. k에서 어떤 자릿수 범위의 전체 문자 개수를 더 이상 뺄 수 없게 되면, 그 범위 안에 답이 존재한다.

5. 정확한 수와 자리 찾기:

• 예를 들어, k가 두 자릿수 범위에 해당한다고 가정한다.

• 남은 k값에 대해, (k-1) ÷ 자릿수(d)의 몫은 “몇 번째 숫자”인지를 알려준다.

• 그 숫자는 해당 자릿수 범위의 시작 숫자(예: 두 자릿수의 시작은 10)에서 “몫”만큼 더한 값이다.

• (k-1) ÷ d의 나머지는 선택한 숫자 내에서 “몇 번째 자리”인지를 가리킨다.

• 해당 숫자를 문자열로 변환한 뒤, 나머지에 해당하는 인덱스 위치의 문자를 결과로 반환한다.

 

이 과정을 통해 k번째 문자를 효율적으로 구할 수 있다.

#include <iostream>
#include <string>

using namespace std;

int n, k;

int main() {
    cin >> n >> k;
    long long nine = 9, digit = 1, num = 1;
    while(k > nine * digit) {
        k -= (nine * digit);
        nine *= 10;
        digit++;
        num *= 10;
    }
    long long idx = (k - 1) / digit;
    num += idx;
    if (num > n || num == 0) { // 수가 큰 경우
        cout << -1;
        return 0;
    }        
    string str = to_string(num);    
    cout << str[(k-1) % digit];    


    return 0;
}