[Inflearn] 숫자의 총 개수(large)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 숫자의 총 개수 small 문제는 최대 N이 100,00 이라서 주먹구구식으로 풀어도 시간초과가 안 났지만, large 문제는 최대 N이 100,000,000 이므로 생각없이 푸는 순간 시간초과가 나도 말 것이다..

 최대한 연산 횟수를 줄이고 풀 수 있는 방법을 생각해보자.

1 ~ 9 : 9 * 1개

10 ~ 99 : 90 * 2개

100 ~ 999 : 900 * 3개

1000 ~ 9999 : 9000 * 4개

N이 333이라면,

N이 p보다 작을 때까지 반복

=> N이 9보다 크다면 + 1 * 9,

     N이 90보다 크다면 + 2 * 90

     N이 999보다 크다면 break;

// p : 자리수를 확인하기 위한 변수

// s : 자리수에 숫자가 몇 개 있는지 확인하는 변수

p = 1, s = 1; 

while(N > 9 * p + p - 1)  // N 이 9, 99, 999, 9999 보다 작을 때까지 반복

    // 1의 자리일 경우 1 * 9

    // 2의 자리일 경우 2 * 90

    // 3의 자리일 경우 3 * 900 이 되려면 규칙을 찾아야 한다.

    // 앞에 1,2,3 은 1씩 증가하고, 9, 90, 900 은 10배씩 증가하는 것을 발견할 수 있다.

    // 이를 식으로 나타내면 s * 9 * p 가 되고, s 는 1씩, p는 10배씩 증가한다. 

    rst += s * 9 * p ;

    p *= 10;

    s++;

// 반복문이 끝나기 전 증가된 p를 이전 값으로

p /= 10;

// N 에서 지금까지 구한 99를 빼준다. 

// ex. N = 333인 경우, 99까지 계산했으므로 아직 계산이 덜 된 숫자를 구하기 위해서는 90 + 10 - 1 = (99) 를 빼줘야하므로, 

        9 * p + p -1 과 같은 식이 나온다.

rem = N - (9 * p + p - 1)

// 다음 자리수에 사용된 숫자를 연산

rst += rem * s;

#. Code

#include<stdio.h>
 
using namespace std;
 
int main() {
    // freopen("input.txt", "rt", stdin);
    int n, rem, rst = 0, p = 1, s = 1;
    
    scanf("%d", &n);
 
    while (n > (9 * p + p - 1))
    {
        rst += s * 9 * p;
        p *= 10;
        s++;
    }
 
    p /= 10;
    rem = n - (9 * p + p - 1);
    rst += rem * s;
 
    printf("%d\n", rst);
 
    return 0;
}

#. Other Code

#include<stdio.h>
 
int main(){
    int n, sum=0, cnt=1, digit=9, res=0;
 
    scanf("%d", &n);
 
    while(sum+digit<n){    
        sum=sum+digit;
        res=res+(cnt*digit);
 
        cnt++;
        digit=digit*10;
    }
 
    res=res+((n-sum)*cnt);
 
    printf("%d\n", res);
 
    return 0;
}

내 코드와 비교하면 가독성에서부터 차이가 나는 것 같다..

나는 엄청 복잡하게 식을 만들었는데...ㅋㅋㅋ

우선 변수 sum 을 사용해서 (9 * p + p - 1) 과 같은 복잡한 식의 사용을 줄였다.

이렇게 로직은 같아도 누가 어떻게 짜느냐에 따라 성능부터 가독성까지 차이가 나는 것 같다..

위 코드를 손디버깅 해보자

 sum    digit    cnt  /  res

  0        9        1       9

  9       90       2      189

  99     900      3 

나머지는 rst + ((n-sum) * cnt) 로 계산해주면 결과가 나온다.

#. Result

  - Input --------------------------------------------------------

15

------------------------------------------------------------------

  - Output --------------------------------------------------------

21

------------------------------------------------------------------