소수와 비소수가 섞여 있는 두 개의 배열이 주어졌을 때, 각 배열에서 소수를 하나씩 골라 만들 수 있는 모든 쌍의 합 중 서로 다른 값(고유한 합계)이 몇 가지인지 구하는 것이 이번 글의 목표입니다.
핵심 아이디어는 단순합니다. 두 배열에서 소수 한 개씩을 짝지어 합을 구하고, 그 값을 중복을 허용하지 않는 set<int>에 저장하는 것입니다. set은 동일한 값을 한 번만 보관하므로, 최종적으로 set의 크기가 곧 고유한 합계의 개수가 됩니다.
문제 이해하기
예제 1
입력
Arr1[] = { 1, 2, 3 }
Arr2[] = { 2, 3, 4 }출력
고유한 소수 합계 : 3
설명
만들 수 있는 소수 쌍은 (2, 2), (2, 3), (3, 2), (3, 3)입니다. 이들의 합은 4, 5, 6 세 가지뿐이므로 정답은 3입니다.
예제 2
입력
Arr1[] = { 1, 4, 6 }
Arr2[] = { 2, 3, 5 }출력
고유한 소수 합계 : 0
설명
Arr1에는 소수가 하나도 없습니다. 소수 쌍 자체가 만들어질 수 없으므로 고유한 합계의 개수는 0이 됩니다.
접근 방법
- 양의 정수로 이루어진 두 배열 Arr1[], Arr2[]와 각각의 길이 len1, len2가 주어집니다.
- isprime(int num) 함수는 num이 소수이면 1, 아니면 0을 반환합니다.
- prime_Sums(int arr1[], int arr2[], int l1, int l2) 함수는 두 배열을 받아 소수 쌍의 고유한 합계 개수를 반환합니다.
- 고유한 합계를 저장하기 위해 set<int> 타입의 sum을 선언합니다.
- 이중 for 루프로 두 배열의 모든 원소 조합을 순회합니다.
- isprime(arr1[i])과 isprime(arr2[j])가 모두 참이라면, 즉 두 원소가 모두 소수라면 tmp = arr1[i] + arr2[j]를 계산합니다.
- sum.insert(tmp)로 합계를 set에 삽입합니다. 이미 저장된 값은 자동으로 무시됩니다.
- 모든 반복이 끝나면 sum.size()를 반환하며, 이 값이 곧 소수 쌍의 고유한 합계 개수입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// num이 소수이면 1, 아니면 0을 반환
int isprime(int num){
if (num <= 1)
return 0;
for (int i = 2; i <= num / 2; i++)
if (num % i == 0)
return 0;
return 1;
}
// 소수 쌍의 고유한 합계 개수를 반환
int prime_Sums(int arr1[], int arr2[], int l1, int l2){
set<int> sum;
for (int i = 0; i < l1; i++){
for (int j = 0; j < l2; j++){
if (isprime(arr1[i]) && isprime(arr2[j])){
int tmp = arr1[i] + arr2[j];
sum.insert(tmp);
}
}
}
return sum.size();
}
int main(){
int Arr1[] = { 2, 3, 5 };
int Arr2[] = { 2, 2, 4, 7 };
int len1 = sizeof(Arr1) / sizeof(Arr1[0]);
int len2 = sizeof(Arr2) / sizeof(Arr2[0]);
cout << "고유한 소수 합계 : " << prime_Sums(Arr1, Arr2, len1, len2);
return 0;
}참고로 원본 예제의 set 선언에는 템플릿 인자가 빠져 있어(set sum;) 컴파일 오류가 발생할 수 있으므로, 위 코드에서는 set<int> sum;으로 바로잡았습니다. 또한 사용되지 않는 count 변수도 함께 제거했습니다.
실행 결과
위 코드를 실행하면 다음과 같은 출력이 나타납니다.
고유한 소수 합계 : 6
Arr1의 소수는 2, 3, 5이고 Arr2의 소수는 2, 2, 7입니다. 이들로 만들 수 있는 합은 4, 9, 5, 10, 7, 12로 여섯 가지이므로 결과는 6입니다.
복잡도와 최적화 팁
이 알고리즘은 두 배열의 모든 쌍을 검사하므로 시간 복잡도는 O(len1 × len2)이며, 여기에 각 원소의 소수 판별 비용이 추가됩니다. 현재 isprime 함수는 2부터 num/2까지 나누어 보는 방식이라 비효율적일 수 있습니다. 소수 판별 범위를 √num까지만 줄이거나, 입력 값의 최대 크기가 제한적이라면 에라토스테네스의 체를 미리 구성해 판별 비용을 상수 시간으로 만드는 것이 좋습니다.