문제 개요
이 문제에서는 N개의 숫자로 이루어진 배열과 하나의 숫자 X가 주어집니다. 우리가 해야 할 일은 배열에 있는 숫자 중 소인수 집합이 X의 소인수 집합의 부분집합이 되는 모든 숫자를 찾아 출력하는 것입니다.
예를 들어 문제를 이해해 보겠습니다.
입력: X = 30, array = {2, 3, 6, 10, 12}
출력: 2 3 6X = 30의 소인수는 2, 3, 5입니다. 따라서 소인수가 2, 3, 5로만 구성된 숫자들만 조건을 만족합니다. 위 예시에서 2, 3, 6은 모두 2와 3으로만 이루어져 있으므로 조건을 충족하지만, 10(=2×5)과 12(=2²×3) 역시 사실 조건을 만족합니다. 핵심은 각 숫자의 모든 소인수가 X의 소인수 집합 안에 포함되어야 한다는 점입니다.
해결 접근 방법
이 문제를 해결하는 가장 효율적인 방법은 최대공약수(GCD)를 활용하는 것입니다. 알고리즘은 다음과 같습니다.
- 배열의 각 요소를 순회합니다.
- 현재 요소와 X의 최대공약수(gcd)를 구합니다.
- 요소를 그 gcd 값으로 나누고, gcd가 1이 될 때까지 이 과정을 반복합니다.
- 최종적으로 남은 수가 1이라면, 해당 숫자의 모든 소인수가 X에 포함된 것이므로 결과로 출력합니다.
이 방법이 작동하는 이유는, 어떤 수와 X의 gcd는 두 수가 공유하는 소인수들의 곱이기 때문입니다. 반복해서 나누다가 1이 되면 더 이상 X에 없는 소인수가 남지 않았다는 의미입니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
void printPrimeSet(int a[], int n, int x){
bool flag = false;
for (int i = 0; i < n; i++) {
int num = a[i];
int g = __gcd(num, x);
while (g != 1) {
num /= g;
g = __gcd(num, x);
}
if (num == 1) {
flag = true;
cout << a[i] << " ";
}
}
if (!flag)
cout << "조건을 만족하는 숫자가 없습니다";
}
int main(){
int x = 60;
int a[] = { 2, 5, 10, 7, 17 };
int n = sizeof(a) / sizeof(a[0]);
cout << "소인수 집합이 " << x << "의 소인수 집합의 부분집합인 숫자들\n";
printPrimeSet(a, n, x);
return 0;
}
실행 결과
60의 소인수 집합의 부분집합이 되는 숫자들:
2 5 10
결과 분석
X = 60의 소인수는 2, 3, 5입니다. 주어진 배열 {2, 5, 10, 7, 17}에서 각 숫자를 살펴보면 다음과 같습니다.
- 2: 소인수가 2뿐이므로 조건 만족 ✓
- 5: 소인수가 5뿐이므로 조건 만족 ✓
- 10: 소인수가 2와 5이므로 조건 만족 ✓
- 7: 7은 60의 소인수가 아니므로 제외 ✗
- 17: 17은 60의 소인수가 아니므로 제외 ✗
따라서 최종 결과로 2, 5, 10이 출력됩니다.
시간 복잡도
각 숫자에 대해 gcd 연산을 반복 수행하며, gcd 계산은 유클리드 호제법 기준 O(log(min(a, b)))의 시간이 걸립니다. 전체 시간 복잡도는 배열 크기 N과 각 숫자의 소인수 개수에 비례하여 대략 O(N × log(max_value)) 수준으로 매우 효율적입니다.