[algorithm 풀이] 3. 3의 개수 구하기

0. 문제

자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자 중 3의 개수가 몇 개 있는지 구하려고 합니다.
예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 3의 개수는 2개입니다.
자연수 N이 입력되면 1부터 N까지 숫자를 적을 때, 3의 개수가 몇 개인지 구하여 출력하는 프로그램을 작성하세요.

1. 입력설명

   • 첫 줄에 자연수의 개수 N(3<=N<=1,000,000,000)이 주어집니다.

2. 출력 설명

   • 3의 개수를 출력하세요.

3. 입력 예제1

   • 15

4. 출력 예제1

   • 2

5. 문제 풀이 핵심

   • 1의 자리~ n의 자리 숫자까지 순회 한며, 각 자리에서 3이 나오는 횟수를 계산한다.
   • i 번째 자리 수를 기준으로 왼쪽과 오른쪽의 숫자로 분리한다.
   • i 번째 자리 수가 3일 경우는 왼쪽의 수와 오른쪽 수의 조합으로 계산 가능하다.

1. 풀이1

1. 사용자에게 num을 입력 받음

2. vector에 각 자리수를 저장

3. 1의 자리 부터 n의 자리까지 순회 아래 반복

4. i 번째 기준 왼쪽 숫자와 오른쪽 숫자로 분리

5. i번째 숫자가 3보다 작으면, 왼쪽 숫자 * 10^i 만큼 3이 발생

6. i번째 숫자가 3이면 왼쪽 숫자*10^i + 오른쪽 숫자 + 1 만큼 발생

7. i번째 숫자가 3보다 크면, 왼쪽 숫자*10^i + 10^i만큼 발생

8. 모든 자리에서 3이 나오는 횟수를 합함

#include<iostream>
#include<vector>
#include<deque>
int main() {
    int num, cnt = 0;;
    scanf_s("%d", &num);
    std::vector<int> a;
    int sum = 0;
    int kk = 1;

   //벡터에 각 자리수 삽입
    while (num > 0) {
        a.push_back(num % 10);
        num = num / 10;
    }

    for (int i = 0; i < a.size(); i++) {
        // 앞의 숫자
        int numFront = 0, n10 = 1;
        for (int j = i + 1; j < a.size(); j++) {
            numFront += a[j] * n10;
            n10 *= 10;
        }

        // 뒤의 숫자
        int numBack = 0;
        for (int j = i - 1; j >= 0; j--) {
            numBack = numBack * 10;
            numBack += a[j];
        }

      //3의 개수 구하기
        sum += numFront * kk;
        if (a[i] == 3) {
            sum += numBack + 1;
        }
        else if (a[i] > 3 ){
            sum += kk;
        }
        kk *= 10;
    }
    std::cout << sum;
    return 0;
}
}

9. 예시
   • 1534의 경우 {4,3,5,1} 형태로 저장
   • i가 0이면(일의 자리 수) 4가 기준이며, 153 , 0 으로 분리
   • 4는 3보다 크므로 3이 나올 경우는 153*10^0 + 10^0 = 154회 발생
   • i가 1이면(십의 자리 수) 3이 기준이며, 15, 4로 분리
   • 3이므로 3이 나올 경우는 15*10^1 + 4 + 1 = 155회 발생
   • i가 2이면(백의 자리 수) 5가 기준이며, 1, 34로 분리
   • 5는 3보다 크므로 3이 나올 경우는 1*10^2 + 10^2 = 200
   • i가 3이면(천의 자리 수) 1이 기준이며, 0 ,534로 분리
   • 1은 3보다 작으므로 3이 나올 경우는 0 * 10^3 = 0
   • 총 509회 발생

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비