C++로 정렬된 두 배열의 상대 여집합(차집합) 구하기

크기가 각각 m과 n인 정렬된 두 배열 arr1과 arr2가 있다고 가정해 봅시다. 이때 두 배열의 상대 여집합(relative complement)을 구해야 합니다. 상대 여집합이란 arr1에는 존재하지만 arr2에는 없는 모든 원소를 의미합니다.

예를 들어 A = [3, 6, 10, 12, 15], B = [1, 3, 5, 10, 16]이라면, A에는 있지만 B에는 없는 원소는 6, 12, 15이므로 결과는 [6, 12, 15]가 됩니다.

이 문제는 본질적으로 집합의 차집합 연산과 동일하기 때문에, C++ STL의 set_difference 함수를 사용하면 매우 간단하게 해결할 수 있습니다.

set_difference 함수란?

set_difference는 <algorithm> 헤더에 포함된 함수로, 첫 번째 정렬된 범위에는 속하지만 두 번째 정렬된 범위에는 속하지 않는 원소들만 출력 반복자(output iterator)에 복사합니다. 두 입력 범위가 모두 오름차순으로 정렬되어 있어야 올바르게 동작한다는 점에 유의해야 합니다.

예제 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
    int first[] = {3, 6, 10, 12, 15};
    int second[] = {1, 3, 5, 10, 16};
    int n = sizeof(first) / sizeof(first[0]);

    vector<int> temp(5);
    vector<int>::iterator it, ls;

    sort(first, first + 5);
    sort(second, second + 5);

    cout << "First array :";
    for (int i = 0; i < n; i++)
        cout << " " << first[i];
    cout << endl;

    cout << "Second array :";
    for (int i = 0; i < n; i++)
        cout << " " << second[i];
    cout << endl;

    ls = set_difference(first, first + 5, second, second + 5, temp.begin());

    cout << "The result of relative complement ";
    for (it = temp.begin(); it < ls; ++it)
        cout << " " << *it;
    cout << endl;
}

실행 결과

First array : 3 6 10 12 15
Second array : 1 3 5 10 16
The result of relative complement 6 12 15

코드 설명

먼저 두 배열을 sort로 오름차순 정렬한 뒤, set_difference에 첫 번째 배열의 시작·끝 반복자와 두 번째 배열의 시작·끝 반복자, 그리고 결과를 저장할 temp.begin()을 전달합니다. 함수는 결과 범위의 끝을 가리키는 반복자를 반환하므로, 반환값 ls까지 순회하면 실제 결과 원소들만 출력할 수 있습니다.

이 방식은 두 배열이 이미 정렬되어 있다는 전제 하에 선형 시간 O(m + n)에 동작하므로 효율적입니다. 만약 배열이 정렬되어 있지 않다면, 정렬에 드는 시간이 추가로 필요하다는 점을 고려해야 합니다.