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

이 튜토리얼에서는 정렬되지 않은 두 배열의 합집합(union)과 교집합(intersection)을 구하는 프로그램을 C++로 작성하는 방법을 단계별로 알아보겠습니다. 먼저 예제를 통해 문제를 이해해 보겠습니다.

문제 예시

입력

arr_one = [1, 2, 3, 4, 5]
arr_two = [3, 4, 5, 6, 7]

출력

union: 1 2 3 4 5 6 7
intersection: 3 4 5

두 배열에 공통으로 포함된 요소는 교집합이 되고, 중복 없이 모든 요소를 합친 결과가 합집합이 됩니다. 그럼 해결 절차를 하나씩 살펴보겠습니다.

합집합(Union) 구하기

• 두 개의 배열을 임의의 값으로 초기화합니다.

• 결과를 저장할 빈 배열 union_result를 생성합니다.

• 첫 번째 배열을 순회하면서 모든 요소를 union_result에 추가합니다.

• 두 번째 배열을 순회하면서, 해당 요소가 아직 union_result에 존재하지 않는 경우에만 추가합니다.

• 최종적으로 union_result 배열을 출력합니다.

교집합(Intersection) 구하기

• 두 개의 배열을 임의의 값으로 초기화합니다.

• 결과를 저장할 빈 배열 intersection_result를 생성합니다.

• 첫 번째 배열을 순회하면서, 해당 요소가 두 번째 배열에도 존재하는 경우에만 추가합니다.

• 최종적으로 intersection_result 배열을 출력합니다.

예제 코드

아래 코드를 통해 전체 구현 과정을 확인할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

// 특정 요소가 배열에 존재하는지 확인하는 함수
int isElementPresentInArray(int arr[], int arr_length, int element) {
    for (int i = 0; i < arr_length; ++i) {
        if (arr[i] == element) {
            return true;
        }
    }
    return false;
}

void findUnionAndIntersection(int arr_one[], int arr_one_length,
                              int arr_two[], int arr_two_length) {
    // 합집합 계산
    int union_result[arr_one_length + arr_two_length] = {};
    for (int i = 0; i < arr_one_length; ++i) {
        union_result[i] = arr_one[i];
    }
    int union_index = arr_one_length;
    for (int i = 0; i < arr_two_length; ++i) {
        if (!isElementPresentInArray(arr_one, arr_one_length, arr_two[i])) {
            union_result[union_index++] = arr_two[i];
        }
    }

    cout << "Union: ";
    for (int i = 0; i < union_index; ++i) {
        cout << union_result[i] << " ";
    }
    cout << endl;

    // 교집합 계산
    int intersection_result[arr_one_length + arr_two_length] = {};
    int intersection_index = 0;
    for (int i = 0; i < arr_one_length; ++i) {
        if (isElementPresentInArray(arr_two, arr_two_length, arr_one[i])) {
            intersection_result[intersection_index++] = arr_one[i];
        }
    }

    cout << "Intersection: ";
    for (int i = 0; i < intersection_index; ++i) {
        cout << intersection_result[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr_one[] = {1, 2, 3, 4, 5};
    int arr_two[] = {3, 4, 5, 6, 7};

    findUnionAndIntersection(arr_one, 5, arr_two, 5);

    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Union: 1 2 3 4 5 6 7
Intersection: 3 4 5

시간 복잡도

이 구현 방식은 각 요소마다 다른 배열을 선형 탐색하므로 시간 복잡도는 O(n × m)입니다. 배열의 크기가 크다면 정렬 후 투 포인터 기법을 사용하거나, std::unordered_set 같은 해시 기반 자료구조를 활용하면 O(n + m)까지 성능을 개선할 수 있습니다.

마무리

지금까지 C++에서 정렬되지 않은 두 배열의 합집합과 교집합을 구하는 방법을 알아보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.