[C++] 3의 개수 구하기

[문제]

자연수 N이 입력되면 1부터 N까지의 자연수를 나열 할 때 3의 개수가 총 몇개인지 출력하는 프로그램을 만들어라.

 

[입력예제]

15

 

[출력예제]

2

 

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개이다.

---

[코드 1]

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int n, count = 1, num, tmp;
    
    //1
    cin >> n;
    
    //3
    if(n>=13){
        for(int i=13; i<=n; i++){
            num=i;
            while(num>0){
                tmp = num%10;
                if(tmp==3) count++;
                num/=10;
            }
        }
    }
    
    //4
    if(n<=2) count = 0;
    
    //5
    cout << count;

    return 0;
}

 

[설명 1]

1. 1부터 N까지의 수 n을 입력받는다.
2. N이 13보다 작은 경우에는 3이 나오는 경우는 한 번 있기 때문에 count변수를 1로 초기화를 시켜두었기에 if문에 들어가지 않는다. 
3. 13과 같거나 큰 경우에는 if문 안의 for문에서 i값을 num에 주고 while문에서 num의 마지막자리 숫자가 3인지 확인하여 count변수를 증가시켜주는것을 반복한다.
4. 만약 입력받은 n이 2와 같거나 작은 경우에는 3이 들어가는 경우가 없기에 count를 0으로 초기화 시켜준다.
5. count를 출력한다.

 

[코드 2 - 시간제한 3초]

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int n, count=0, left, right, now, ten=1;
    
    //1
    cin >> n;
    
    //2
    while(left!=0){
        //3
    	left = n/(ten*10);
        //4
    	right = n%ten;
        //5
    	now = (n/ten)%10;
        //6
    	if(now > 3) count = count+((left+1)*ten);
    	else if(now==3) count = count+(left*ten)+(right+1);
    	else count = count+(left*ten);
        //7
    	ten = ten*10;
	}
    
    //8
    cout << count;

	return 0;
}

[설명 2]

해당 코드는 시간복잡도를 줄이기 위해 변경시킨 코드이다.

숫자를 입력받으면 일의 자리 수 부터 중심이 되는 숫자(now)로 정해 준 후 now를 기준으로 left와 right로 나눠준다.

now변수를 왼쪽으로 한칸씩 옮겨가며 if문의 조건에 맞춰 now를 확인 하여 count변수에 3의 개수를 더해주는 방식이다.

예를 들어 34란 숫자를 n값으로 입력받으면 현재 now는 4이고 4는 3보다 큰 경우이니 count = (3+1)*1로 4개가 된다.

실제로 1부터 34에는 3, 13, 23, 33으로 일의 자리에 3이 들어오는 경우는 4번이다.

다음으로 now는 3이 되고 count = (0*10)+(4+1)로 5개가 된다. 10의 자리에 3이 오는 경우는 30, 31, 32, 33, 34로 십의 자리에 3이 들어오는 경우는 5번이다.

1. n을 입력받는다.
2. left변수가 0이 아닐때까지 반복한다.
3. left변수에는 입력받은 숫자의 중심되는 숫자(now) 왼편을 저장한다.
4. right변수에는 입력받은 숫자의 중심되는 숫자(now) 오른편을 저장한다.
5. now변수에는 현재 중심이 되는 숫자를 저장한다.
6. now의 숫자를 if문 조건에 맞춰 count변수에 3의 개수를 넣어준다.
7. ten에 10을 곱하여 now, left, right를 변경시키며 반복문을 진행해준다.
8. count를 출력한다.

 

[출력 결과]