이 문제에서는 두 개의 배열 arr1[]과 arr2[]가 주어집니다. 우리의 과제는 다른 배열의 어떤 요소로도 나누어지지 않는 배열의 요소를 찾는 프로그램을 작성하는 것입니다.
문제 설명: arr1의 모든 요소 중에서 arr2의 어떤 요소로도 나누어 떨어지지 않는 요소들을 전부 찾아 출력해야 합니다.
예시를 통한 문제 이해
입력: arr1[] = {17, 15, 5, 12, 8} arr2[] = {5, 4}
출력: 17
설명 −
arr1의 각 요소와 이를 나누는 arr2의 요소는 다음과 같습니다.
17 → 나눌 수 있는 요소가 없습니다.
15 → 5로 나누어집니다.
5 → 5로 나누어집니다.
12 → 4로 나누어집니다.
8 → 4로 나누어집니다.
따라서 arr2의 어떤 요소로도 나누어지지 않는 유일한 값인 17이 결과가 됩니다.
해결 접근 방법 −
이 문제를 해결하는 가장 단순하고 직관적인 방법은 직접 비교 방식입니다. arr1을 순회하면서 각 요소마다 arr2의 어떤 요소가 해당 값을 나누는지 일일이 확인합니다. 나눌 수 있는 요소가 하나도 없다면 그 요소를 출력합니다.
알고리즘 −
1단계: arr1을 순회합니다. i → 0부터 n-1까지.
2.1단계: 각 arr1[i]에 대해 arr2를 순회합니다. j → 0부터 m-1까지.
2.2단계: 만약 arr1[i] % arr2[j] == 0이라면 flag = -1로 설정하고 내부 반복문을 종료합니다.
2.3단계: flag != -1이라면 arr1[i]를 출력합니다.
솔루션 동작 예시 프로그램
예제
#include<iostream>
using namespace std;
void findEleNotDivisbleByArray(int arr1[], int arr2[], int arr1Size, int arr2Size) {
int flag = 0;
for (int i = 0; i < arr1Size; i++) {
flag = 0;
for (int j = 0; j < arr2Size; j++){
if( arr1[i] % arr2[j] == 0 ) {
flag = -1;
break;
}
}
if ( flag == 0 )
cout<<arr1[i]<<"\t";
}
}
int main()
{
int arr1[] = {17, 15, 5, 12, 23, 8};
int arr2[] = {5, 4};
int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
cout<<"다른 배열의 어떤 요소로도 나누어지지 않는 배열의 요소는 ";
findEleNotDivisbleByArray(arr1, arr2, arr1Size, arr2Size);
return 0;
}출력 −
다른 배열의 어떤 요소로도 나누어지지 않는 배열의 요소는 17 23
이 방법의 시간 복잡도는 O(n × m)으로, 두 배열의 크기가 커질수록 성능이 급격히 저하됩니다. 이 솔루션은 올바르지만 효율적이지 않으므로, 더 개선된 해결 방법을 살펴보겠습니다.
효율적인 해결 방법 −
두 번째 방법은 에라토스테네스의 체(Sieve of Eratosthenes)와 유사한 아이디어를 활용합니다. 먼저 arr1의 최댓값을 구한 뒤, 그 크기만큼의 마킹 배열 mark[]를 생성합니다. 그다음 arr2의 모든 요소에 대해 arr1의 최댓값까지의 배수들을 모두 표시합니다. 마지막으로 mark 배열에서 표시되지 않은 arr1의 요소들만 출력하면 됩니다.
이 방식은 나눗셈 연산 대신 단순한 배열 인덱스 접근만 사용하므로, 특히 arr2의 요소 개수가 많거나 arr1의 최댓값이 크지 않은 경우 상당한 성능 향상을 기대할 수 있습니다.
솔루션 동작 예시 프로그램
예제
#include<iostream>
using namespace std;
void findEleNotDivisbleByArray(int arr1[], int arr2[], int arr1Size, int arr2Size) {
int maxEle = 0;
for (int i = 0; i < arr1Size; i++)
if (arr1[i] > maxEle)
maxEle = arr1[i];
int mark[maxEle];
for (int i = 0; i < arr2Size; i++)
for (int j = arr2[i]; j <= maxEle; j += arr2[i])
mark[j] = 1;
for (int i = 0; i < arr1Size; i++)
if ( mark[arr1[i]] != 1)
cout << arr1[i] << endl;
}
int main()
{
int arr1[] = {17, 15, 5, 12, 8};
int arr2[] = {5, 4};
int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
cout<<"다른 배열의 어떤 요소로도 나누어지지 않는 배열의 요소는 ";
findEleNotDivisbleByArray(arr1, arr2, arr1Size, arr2Size);
return 0;
}출력 −
다른 배열의 어떤 요소로도 나누어지지 않는 배열의 요소는 17
정리하면, 단순 이중 반복문 기반의 무차별 대입 방식은 구현이 쉽지만 O(n × m)의 시간이 걸리는 반면, 체 방식을 응용한 마킹 기법은 배수만 순회하므로 실제 연산 횟수를 크게 줄여 더 빠른 실행 속도를 제공합니다.