[Inflearn] 3의 개수는?(small) (Google interview source)

#. 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. 최대 N이 100,000 이고 각 자리수를 10으로 나누면서 3이 있는지 확인하기 위해서는 N까지의 반복문 안에

     최대 5번의 반복문이 돌 것이다. 문제도 small 이라고 되어있는 것을 보면 그냥 풀어도 풀릴 것 같다.

     단, 최대 N이 커진다면 이 문제는 단순하게 풀리진 않을 것이다.

     일단 N까지 10으로 나누면서 3의 개수를 구해보자.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int main(void) {     //freopen("input.txt", "rt", stdin);       int n, i, num, cnt = 0;       scanf("%d", &n);       for (i = 1; i <= n; i++)     {         num = i;           while (num)         {             if (num % 10 == 3)                 cnt++;               num /= 10;         }     }       printf("%d\n", cnt);       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include<stdio.h> #include<vector> #include<algorithm>   using namespace std;   int main(){     int n, tmp, i, cnt=0, digit;       scanf("%d", &n);       for(i=1; i<=n; i++){         tmp=i;           while(tmp>0){             digit=tmp%10;               if(digit==3) cnt++;               tmp=tmp/10;         }     }       printf("%d\n", cnt);       return 0; }

cs

이전에도 유사한 문제를 풀었기 때문에 코드가 거의 똑같다ㅋ..ㅋ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include<stdio.h>   int res;   int main(){     int n, i, j;       scanf("%d", &n);       for(i=1; i<=n; i++){         for(j=i; j>0; j=j/10){             if(j%10==3) res++;         }     }       printf("%d\n", res);       return 0; }

cs

위 방법과 동일하지만 for문을 두 번 사용한 형태이다.

while 대신 for 문을 사용한 형태라 똑같다고 보면 될 것 같다.

#. Result

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

15

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

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

2

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