숫자 N이 주어졌을 때, 그 숫자를 구성하는 자릿수 중에서 N을 나눌 수 있는 자릿수의 개수를 구하는 것이 이번 문제의 목표입니다.
기억해야 할 핵심 사항
자릿수가 0인 경우에는 무시합니다. 즉, 0에 대해서는 카운트가 증가하지 않습니다.
동일한 자릿수가 여러 번 나타나고 그 자릿수가 숫자를 나눌 수 있다면, 카운트는 해당 자릿수가 나타난 횟수만큼 증가합니다. 예를 들어 숫자 2240이 주어지면, 0을 제외한 모든 자릿수가 2240을 나눌 수 있으며, 2가 두 번 나타나므로 자릿수 2에 대한 카운트는 2가 됩니다.
입력 − number = 2240
출력 − 개수는 3
설명 − 숫자를 자릿수 단위로 분해하면 2, 2, 4, 0이 됩니다. 이제 2가 2240을 나눌 수 있는지 확인하고, 나눌 수 있으면 카운트를 1 증가시키고, 그렇지 않으면 다음 자릿수로 넘어갑니다. 이 숫자에서는 2, 2, 4가 2240을 나눌 수 있으므로 카운트는 3이 되며, 모든 경우에 자릿수 0은 무시합니다.
입력 − number = 755
출력 − 개수는 2
설명 − 숫자를 자릿수 단위로 분해하면 7, 5, 5가 됩니다. 이제 7이 755를 나눌 수 있는지 확인하고, 나눌 수 있으면 카운트를 1 증가시키고, 그렇지 않으면 다음 자릿수로 넘어갑니다. 이 숫자에서는 5, 5가 755를 나눌 수 있으므로 카운트는 2가 되며, 모든 경우에 자릿수 0은 무시합니다.
프로그램에서 사용된 접근 방식
정수형 변수(예: num)에 숫자를 입력받습니다.
num이 0보다 큰 동안 반복문을 실행합니다.
반복문 안에서 숫자를 자릿수 단위로 분해하고 그 결과를 변수(예: rem)에 저장합니다.
rem이 원래 숫자를 나눌 수 있는지 확인합니다. 나눌 수 있다면 count 변수의 값을 1 증가시키고, 그렇지 않으면 증가시키지 않습니다.
이 검사 조건은 0으로 나누는 오류를 피하고 0을 무시해야 하기 때문에 rem이 0보다 클 때만 적용됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int count(int num){
int a=num;
int count=0,rem;
while(a>0){
rem=a%10;
if(rem > 0){
if(num%rem==0){
count++;
}
}
a=a/10;
}
return count;
}
int main(){
int num = 2240;
cout<<"Count of digits in given number "<<num<<" which divide N are: "<<count(num);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다 −
Count of digits in given number 2240 which divide N are: 3
시간 및 공간 복잡도
이 알고리즘은 숫자의 자릿수만큼 한 번씩 반복하므로 시간 복잡도는 O(log₁₀N)입니다. 추가적인 저장 공간을 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.