C++ STL의 set_difference()로 두 배열의 차집합 구하기: 첫 번째 배열에만 있는 요소 찾기

개요

두 개의 배열이 주어졌을 때, 두 배열을 서로 비교하여 첫 번째 배열에는 존재하지만 두 번째 배열에는 없는 숫자를 찾아야 합니다. 이 글에서는 C++의 표준 템플릿 라이브러리(STL)를 활용해 이 문제를 효율적으로 해결하는 방법을 살펴보겠습니다.

예제

입력: array1[ ] = {1, 2, 3, 4, 5, 7}
      array2[ ] = {2, 3, 4, 5, 6, 8}
출력: 1, 7

입력: array1[ ] = {1, 20, 33, 45, 67}
      array2[ ] = {1, 12, 13, 114, 15, 13}
출력: 20, 33, 45, 67

문제 해결 접근 방식

이 프로그램의 목표는 첫 번째 배열에는 있지만 두 번째 배열에는 없는 요소를 찾아내는 것입니다. 해결 과정은 다음과 같습니다.

먼저 필요한 변수들을 초기화하고, 첫 번째 배열에는 있고 두 번째 배열에는 없는 요소를 찾아내는 find라는 이름의 함수를 작성합니다.
함수 내부에서는 결과를 저장할 벡터(vector)를 선언합니다. 벡터는 요소가 삽입되거나 삭제될 때 자동으로 크기가 조절되는 동적 배열과 유사한 자료구조입니다.
벡터의 요소를 순회하기 위한 반복자(iterator)도 함께 선언합니다.
두 배열을 각각 정렬한 후, STL의 set_difference( ) 메서드를 사용해 누락된 요소를 찾고, 그 결과 개수에 맞게 벡터의 크기를 조정한 뒤 값을 저장합니다.
마지막으로 결과 벡터를 순회하며 답을 출력합니다.

set_difference( ) 메서드란?

STL에서는 set_difference( ) 메서드를 사용해 "array1 − array2", 즉 두 집합의 차집합을 손쉽게 구할 수 있습니다. 두 집합의 차집합은 첫 번째 집합에는 존재하지만 두 번째 집합에는 없는 요소들로 구성됩니다. 이 함수가 복사하는 요소는 항상 첫 번째 범위에서 가져오며, 원래의 순서가 그대로 유지됩니다. 단, 이 메서드를 사용하려면 두 범위의 요소들이 이미 정렬되어 있어야 한다는 점에 유의해야 합니다.

구문

set_difference( )의 구문은 다음과 같습니다.

OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
                               InputIterator2 first2, InputIterator2 last2,
                               OutputIterator result);

알고리즘

시작
단계 1 -> 누락된 요소를 찾는 함수 생성
    void find(int array1[], int array2[], int x, int y)
    결과를 저장할 벡터를 vector<int> v(x + y)로 선언
    벡터를 순회할 반복자를 vector<int>::iterator로 선언
    두 배열을 정렬
        sort(array1, ...), sort(array2, ...)
    종료
    누락된 요소 찾기
        diff = set_difference(array1, array1 + x, array2, array2 + y, v.begin())
    실제 요소 개수에 맞게 벡터 크기 조정
        v.resize(diff - v.begin())
    array1[]에는 있고 array2[]에는 없는 요소 출력
        for (diff = v.begin(); diff != v.end(); ++diff)
            *diff 출력
        종료
단계 2 -> main() 함수에서
    배열을 int array1, int array2로 선언
    배열 크기를 계산할 변수 x와 y 선언
        int x = array1의 크기, int y = array2의 크기
    find(array1, array2, x, y) 형태로 함수 호출

C++ 구현 예제

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

// 누락된 요소를 찾기 위한 "find" 함수 생성
void find(int array1[], int array2[], int x, int y) {
   // 결과를 저장할 벡터 선언
   vector<int> v(x + y);
   // 벡터를 순회할 반복자 선언
   vector<int>::iterator diff;
   // 두 배열 정렬
   sort(array1, array1 + x);
   sort(array2, array2 + y);
   // 누락된 요소 찾기
   diff = set_difference(array1, array1 + x, array2, array2 + y, v.begin());
   // 실제 요소 개수에 맞게 벡터 크기 조정
   v.resize(diff - v.begin());
   cout << "array1[]에는 있고 array2[]에는 없는 요소: ";
   for (diff = v.begin(); diff != v.end(); ++diff)
      cout << *diff << " ";
   cout << endl;
}

int main() {
   int array1[] = { 1, 2, 3, 4, 5, 7 };
   int array2[] = { 2, 3, 4, 5, 6, 8 };
   int x = sizeof(array1) / sizeof(array1[0]);
   int y = sizeof(array2) / sizeof(array2[0]);
   find(array1, array2, x, y);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

array1[]에는 있고 array2[]에는 없는 요소: 1 7

이처럼 STL의 set_difference( )를 활용하면 복잡한 반복문 없이도 두 배열의 차집합을 간결하고 효율적으로 구할 수 있습니다. 단, 반드시 두 배열이 사전에 정렬되어 있어야 올바른 결과를 얻을 수 있다는 점을 기억하세요.