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

백준

 

---

🤔문제 이해

1부터 N까지 숫자를 이어써서 만든 수의 k번째 자리의 숫자를 구하는 문제!

문제가 짧은 만큼 간단했다.

---

💡첫번째 아이디어

간단하게 생각했을 때 N의 자릿수가 n일 때 새롭게 만들어지는 수는 1*9 + 2*90 + 3*900 + ... (n-1)*((10^n -1)-(10^n-2))에 가장 작은 n자리 수부터 n까지를 더하면 구할 수 있을 것이라고 생각했다.

k를 찾을 때에는 k가 포함되는 곳이 몇 자릿수일 때인지를 파악해서 최악의 경우 10000000~9999999까지 탐색하므로 시간 제한에 걸리지 않을 것이라고 판단했다.

 

 

🔥풀이🔥

첫번째 반복문 

-> k가 포함되는 자릿수 구하기

두번째 반복문 

-> 해당 자릿수의 최솟값~최댓값까지 total에 자릿수를 더해주면서 k가 포함되는 범위를 찾고 total과 k가 같아지는 시점의 숫자를 출력

 

1의 자리의 경우 k가 n보다 크다면 -1, 그렇지 않다면 k를 출력하게 따로 빼주었다.

 

 

❌첫번째~세번째 제출(6%에서 틀렸습니다.)

풀이 방법대로 구현했는데 두번째 반복문에서 k의 범위를 확인할 때와 total에 해당 자릿수만큼 더해주는 식에서 현재 자릿수가 아닌 입력받은 n의 자릿수를 더해줘서 틀렸었다...ㅎ

 

⭕️네번째 제출(맞았습니다!!)

맞추긴 했는데 시간이 1052ms~1053ms가 떴다...

다른 사람은 0ms에 대부분 풀었길래 조금만 더 생각해보기로 했다.

---

💡두번째 아이디어

뭔가 n에서 k가 해당되는 자릿수-1까지의 숫자의 개수를 빼보면 뭔가 구할 수 있을 것 같았다!

n-total를 해서 자릿수로 나누고, 나머지를 구했다.

몫은 해당 자릿수의 최솟값(ex. 2자리인 경우 10)에 +몫만큼 해줬을 때 k 범위에 해당하는 숫자가 나왔다. 

나머지는 k 범위에 해당하는 숫자의 몇번째 자리가 k인지를 나타내주었다.

 

❌여섯번째~일곱번째 제출(6%에서 틀렸습니다.)

구현하는데서 막혀버렸따🙄

해야할 일이 산더미라 다른 사람의 코드를 참고했다. 나랑 아이디어는 같은 거 같은데... 

 

 

⭕️여덟번째 제출(맞았습니다!!)

앞으로 문제 푸는 연습을 더 많이 해야 할 것 같다. 이 실력으론 다음 학기 알고리즘도 힘들듯^^;;

 

---

 

 

아래는 첫번째 아이디어로 제출한 코드이다. 

//
// Created by 김유리 on 2022/07/11.
//
#include <iostream>
#include <math.h>

using namespace std;

long long n, k;
long long total;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n >> k;
    string str = to_string(n);
    long long i;
    for (i = 1; i <= str.size(); i++) {
        if (total < k && total + i * ((long long) pow(10, i) - (long long) pow(10, i - 1)) >= k) {
            break;
        } else {
            total += i * ((long long) pow(10, i) - (long long) pow(10, i - 1));
        }
    }
    if (total == 0) {
        if (k > n) {
            cout << -1;
        } else {
            cout << k;
        }
        return 0;
    }
    for (int j = pow(10, i - 1); j <= n; j++) {
        string num = to_string(j);
        if (total < k && total + num.size() >= k) {
            for (int l = 0; l < num.size(); l++) {
                total++;
                if (total == k) {
                    cout << num[l];
                    return 0;
                }
            }
        } else {
            total = total + num.size();
        }
    }
    cout << -1;
    return 0;


}