부분집합 판별 함수 - Includes

알고리즘 문제를 풀면서 배열 간의 부분집합 여부를 판별해야 할 때가 있다. 그럴 때 사용할 수 있는 좋은 함수를 발견해서 한번 정리해보려고 한다.

 

std::includes() 함수는 <algorithm> 헤더에 있는 함수로, 원형은 아래와 같이 생겼다.

 

template<class InputIt1, class InputIt2, class Compare>
bool includes(InputIt1 first1, InputIt1 last1,
              InputIt2 first2, InputIt2 last2, Compare comp)
{
    for (; first2 != last2; ++first1)
    {
        if (first1 == last1 || comp(*first2, *first1))
            return false;
        if (!comp(*first1, *first2))
            ++first2;
    }
    return true;
}

 

이 함수는 4개의 인자 first1, last1, first2, last2를 받도록 되어있는데, 전체 집합이 되는 배열을 A, 부분 집합이 되는 배열을 B라 하면 차례대로 A의 시작 iterator, A의 끝 iterator, B의 시작 iterator, A의 끝 iterator를 받는다.

 

예를 들어 배열 A와 B가 아래와 같이 되어있다고 생각해보자.

 

int A[5]={1, 2, 3, 4 ,5};
int B[3]={1, 2, 3};

 

이때 includes(A.begin(), A.end(), B.begin(), B.end()); 를 사용하면 배열 B가 배열 A의 부분집합이 될 수 있는지 판정하여 될 수 있으면 true, 그렇지 않으면 false를 리턴한다.

 

includes 함수를 사용할 때 주의할 점은 배열 A와 B가 정렬되어있는 상태여야 한다는 것이다. 위의 원형 함수에서 보면 이유를 알 수 있는데, first1을 1씩 더해가며 A[first1]과 B[first2]를 비교하고 같으면 first2를 늘리고, 다르면 바로 false를 리턴하는 식이다. 두 배열이 정렬되어 있지 않다면 이러한 방식의 비교가 불가능하므로, 두 배열은 정렬되어 있어야 한다.