C++에서 주어진 수를 나눌 수 있는 자릿수의 개수 구하기

어떤 수가 주어졌을 때, 그 수의 각 자릿수 중에서 원래의 수를 나머지 없이 정확히 나눌 수 있는 자릿수의 개수를 세는 문제입니다. 예를 들어 1012가 주어지면 결과는 3이 됩니다. 자릿수 1, 1, 2가 각각 1012를 나누어 떨어지게 하기 때문입니다.

이 문제를 해결하려면 모듈로(%) 연산을 이용해 각 자릿수를 하나씩 추출하고, 해당 자릿수로 원래의 수가 나누어 떨어지는지 확인합니다. 나누어 떨어지면 카운터를 증가시키고, 마지막에 카운터 값을 반환하면 됩니다. 단, 자릿수가 0인 경우에는 0으로 나눌 수 없으므로 반드시 건너뛰어야 합니다.

알고리즘 동작 방식

숫자를 10으로 나눈 나머지를 구하면 가장 오른쪽 자릿수를 얻을 수 있고, 숫자를 10으로 나누면 그 자릿수가 제거됩니다. 이 과정을 숫자가 0이 될 때까지 반복하면서 각 자릿수에 대해 나눗셈 가능 여부를 검사합니다. 이 알고리즘의 시간 복잡도는 자릿수의 개수에 비례하므로 O(log N)입니다.

예제 코드

#include<iostream>
using namespace std;

int countDivDigit(int num) {
    int count = 0;
    int temp = num;
    while(temp){
        int div = temp % 10;   // 마지막 자릿수 추출
        if(div != 0){          // 0으로 나누는 경우 방지
            if(num % div == 0)
                count++;
        }
        temp /= 10;            // 다음 자릿수로 이동
    }
    return count;
}

int main() {
    int num = 1012;
    cout << "Number of digits that divides " << num << " evenly, is: " << countDivDigit(num);
}

실행 결과

Number of digits that divides 1012 evenly, is: 3

코드 설명

위 코드에서 countDivDigit 함수는 원본 숫자를 변경하지 않기 위해 임시 변수 temp에 값을 복사한 후 사용합니다. while 루프 안에서 temp % 10으로 현재 자릿수를 구하고, 그 값이 0이 아닐 때만 num % div == 0 조건을 검사합니다. 조건을 만족하면 카운트를 증가시키고, temp /= 10으로 이미 확인한 자릿수를 제거하여 다음 자릿수를 처리합니다. 모든 자릿수를 확인한 후 최종 카운트를 반환합니다.