C++로 두 배열 비교하기: 첫 번째 배열에만 있는 요소 찾는 방법

두 개의 배열 A와 B가 있다고 가정해 봅시다. 이때 배열 A에는 존재하지만 배열 B에는 없는 요소들을 찾아야 합니다. A와 B를 집합(set)으로 생각하면, 이 작업은 기본적으로 집합 차집합 연산과 같습니다. 즉, A와 B의 차집합을 구하면 원하는 요소들을 얻을 수 있습니다.

C++에서는 <algorithm> 헤더에 포함된 std::set_difference 함수를 사용하면 이 작업을 간단하게 처리할 수 있습니다. 다만 이 함수를 사용하기 전에는 반드시 두 배열이 정렬되어 있어야 한다는 점에 유의해야 합니다.

예제 코드

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

void setDiffResults(int A[], int B[], int An, int Bn) {
    sort(A, A + An);
    sort(B, B + Bn);
    vector<int> res(An);
    vector<int>::iterator it;
    vector<int>::iterator it_res = set_difference(A, A + An, B, B + Bn, res.begin());
    cout << "Elements are: ";
    for(it = res.begin(); it < it_res; ++it){
        cout << *it << " ";
    }
}

int main() {
    int A[] = {9, 4, 5, 3, 1, 7, 6};
    int B[] = {9, 3, 5};
    int An = 7, Bn = 3;
    setDiffResults(A, B, An, Bn);
}

실행 결과

Elements are: 1 4 6 7

코드 설명

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1. 정렬: set_difference는 정렬된 범위에서만 올바르게 동작하므로, 먼저 sort()를 이용해 배열 A와 B를 오름차순으로 정렬합니다.

2. 결과 저장 공간 준비: 차집합 결과를 담을 벡터 res를 배열 A의 크기(An)만큼 미리 할당합니다. 차집합의 최대 크기는 A의 크기를 넘지 않기 때문입니다.

3. 차집합 계산: set_difference(A, A + An, B, B + Bn, res.begin())은 A에는 있지만 B에는 없는 요소들을 찾아 res에 저장하고, 결과의 끝 위치를 가리키는 반복자(iterator)를 반환합니다.

4. 결과 출력: 반환된 반복자 it_res까지 순회하며 결과 요소들을 출력합니다.

이 예제에서 배열 A = {9, 4, 5, 3, 1, 7, 6}과 배열 B = {9, 3, 5}를 비교한 결과, A에만 존재하는 요소인 1, 4, 6, 7이 출력됩니다. 시간 복잡도는 정렬에 O(N log N), 차집합 연산에 O(N + M)이 소요되므로 전체적으로 O(N log N)입니다.