C++로 구현하는 정렬되지 않은 두 배열의 합집합과 교집합 찾기

개요

이 글에서는 정렬되지 않은 두 개의 배열이 주어졌을 때, 두 배열의 합집합(union)과 교집합(intersection)을 구하는 C++ 프로그램을 살펴봅니다.

두 배열을 각각 'A'와 'B'라고 하겠습니다. 두 배열의 합집합은 A ∪ B로 표현되며, 두 배열에 포함된 모든 원소를 담되 각 원소는 중복 없이 한 번만 나타나는 배열을 의미합니다.

합집합을 구하는 방법은 다음과 같습니다. 먼저 별도의 배열을 만들어 첫 번째 배열의 모든 원소를 복사해 넣습니다. 그다음 두 번째 배열의 원소를 하나씩 순회하면서 해당 원소가 합집합 배열에 이미 존재하는지 확인하고, 존재하지 않는 경우에만 새로 추가합니다.

마찬가지로 두 배열의 교집합은 A ∩ B로 표현되며, 두 배열 모두에 공통으로 존재하는 원소들로만 이루어진 배열입니다.

교집합을 구할 때는 첫 번째 배열의 원소를 하나씩 순회하면서, 동시에 그 원소가 두 번째 배열에도 존재하는지 검사합니다. 양쪽 배열 모두에 있는 원소라면 교집합 배열에 추가합니다.

예제 코드

#include <iostream>
using namespace std;
int main() {
    int len1 = 4, len2 = 3, flag1 = 0, flag2 = 0;
    int array1[len1] = {1,2,3,4}, array2[len2] = {5,3,4};
    int uni[len1+len2] = {1,2,3,4}, inter[len1];
    for(int k = 0; k < len2 ; k++) {
        flag1 = len1;
        for(int m = 0; m < len1; m++) {
            //두 배열 사이의 중복 원소 제거
            if(array2[k] == uni[m])
                break;
            else if(m == len1-1) {
                uni[flag1] = array2[k];
                flag1 = flag1+1;
            }
        }
    }
    for(int q = 0; q < len1; q++) {
        for(int w = 0; w < len2; w++) {
            //특정 원소가 두 배열 모두에 존재하는지 확인
            if(array1[q] == array2[w]) {
                inter[flag2] = array1[q];
                flag2 = flag2+1;
                break;
            }
        }
    }
    cout << "Union :" <<endl;
    for(int u = 0; u < flag1; u++) {
        cout << uni[u] << " ";
    }
    cout << "\nIntersection :" <<endl;
    for(int i = 0; i < flag2; i++) {
        cout << inter[i] << " ";
    }
    return 0;
}

실행 결과

Union :
1 2 3 4
Intersection :
3 4

시간 복잡도

위 코드는 이중 반복문을 사용해 각 원소의 존재 여부를 일일이 비교하기 때문에, 배열의 크기를 각각 n과 m이라 할 때 시간 복잡도는 O(n × m)입니다.

배열의 크기가 큰 경우에는 해시 셋(set 또는 unordered_set)을 활용하면 평균적으로 O(n + m)까지 성능을 개선할 수 있습니다. 다만 위 예제처럼 단순한 입력 크기에서는 이중 반복문 방식도 충분히 실용적입니다.