문제 소개
정수 num이 하나 주어집니다. 해야 할 일은 이 수의 모든 약수를 구한 뒤, 그중에서 num의 자릿수와 최소 한 개 이상 공통된 숫자를 포함하는 약수의 개수를 세는 것입니다.
예시 1
입력 — num = 24
출력 — 개수는 4
풀이 과정은 다음과 같습니다.
- 먼저 주어진 수의 약수를 모두 구합니다.
→ 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24 - 다음으로, 각 약수가 num의 자릿수(2, 4)와 일치하는 숫자를 하나라도 포함하는지 확인합니다.
→ 조건을 만족하는 약수는 2, 4, 12, 24이며, 따라서 개수는 4입니다.
예시 2
입력 — num = 10
출력 — 개수는 2
풀이 과정은 다음과 같습니다.
- 먼저 주어진 수의 약수를 모두 구합니다.
→ 10의 약수: 1, 2, 5, 10 - 다음으로, 각 약수가 num의 자릿수(1, 0)와 일치하는 숫자를 하나라도 포함하는지 확인합니다.
→ 조건을 만족하는 약수는 1, 10이며, 따라서 개수는 2입니다.
접근 방법
효율적인 풀이를 위해 다음 알고리즘을 사용할 수 있습니다.
- 주어진 수 num의 각 자릿수를 크기 10의 배열(arr)에 표시합니다. 예를 들어 num = 24라면 arr[2]와 arr[4]가 1로 설정됩니다.
- 1부터 √num까지의 수 i를 순회하며 num % i == 0일 때 i와 num/i가 모두 약수라는 성질을 이용해 약수를 찾습니다. 제곱근까지만 확인하면 시간 복잡도를 O(√n)으로 줄일 수 있습니다.
- 각 약수에 대해 digitCheck() 함수를 호출해 해당 약수의 자릿수 중 하나라도 arr에서 1로 표시된 숫자와 일치하는지 검사하고, 일치하면 카운트를 증가시킵니다.
예제 코드
package test;
import java.util.*;
import java.util.Scanner;
public class Testdigit {
static int digitCheck(int m, int arr[]) {
while (m > 0) {
if (arr[m % 10] == 1) {
return 1;
}
m = m / 10;
}
return 0;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("Enter any number: ");
int n = scan.nextInt();
int arr[] = new int[10];
int m = n;
while (m > 0) {
arr[m % 10] = 1;
m = m / 10;
}
int count = 0;
for (int i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
if (digitCheck(i, arr) == 1) {
count++;
}
if (n / i != i) {
if (digitCheck(n / i, arr) == 1) {
count++;
}
}
}
}
System.out.println("Count " + count);
}
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Enter any number: 24 Count 4
복잡도 분석
약수 탐색에 O(√n), 각 약수의 자릿수 검사에 O(log n)이 소요되므로 전체 시간 복잡도는 O(√n × log n)입니다. 자릿수 표시에 사용되는 배열의 크기는 항상 10으로 고정되어 있으므로 공간 복잡도는 O(1)입니다.