<C++ 알고리즘> 진부분집합 구하기

A가 B에 진부분집합인지를 판단하는 함수 정의

 

 

#include <iostream>
#include <set>

using namespace std;

// 배열을 활용
const bool IsProperSubsetOf(const int* ArrSrc, const int SrcSize, 
    const int* ArrDest, const int DestSize, int& Iter)
{
   // 예외처리(DestSize가 SrcSize보다 작다면)
   if (DestSize < SrcSize)
        return false;

   for (int i = 0; i <= DestSize - SrcSize; ++i)
   {
       int Count = 0;
       for (int j = i; j < SrcSize + i; ++j)
       {
           ++Iter;
           if (ArrSrc[Count] != ArrDest[j])
               break;
           else
           {
               ++Count;

               if (Count == SrcSize && Count != DestSize)
                   return true;
           }
       }
   }

   return false;
}

// set을 활용
// 중복 값은 유일한 값이 된다. 값을 넣고 나서 비교 값이 그대로 라면 Dest가 Src를 포함하고 있다는 것이다.
// 빅오 표기법 O(n)
const bool IsProperSubsetOf(const int* ArrSrc, const int& SrcSize, set<int>& SetDest, int& Iter)
{
    // 예외 처리
    if (SetDest.size() < static_cast<size_t>(SrcSize))
        return false;

    set<int> setDestCopy(SetDest);

    for (int i = 0; i < SrcSize; ++i)
    {
        ++Iter;
        setDestCopy.insert(ArrSrc[i]);
    }

    if (setDestCopy.size() > static_cast<size_t>(SrcSize))
        return true;

    return false;
}

// 출력 함수
void printIsProperSubsetOf(const int* ArrSrc, const int SrcSize,
    const int* ArrDest, const int DestSize)
{
    int iter = 0;
    cout << "(" << iter << ", " << boolalpha << IsProperSubsetOf(ArrSrc, SrcSize, ArrDest, DestSize, iter) << ")" << endl;
}

void printIsProperSubsetOf(const int* ArrSrc, const int& SrcSize, set<int>& SetDest)
{
    int iter = 0;
    cout << "(" << iter << ", " << boolalpha << IsProperSubsetOf(ArrSrc, SrcSize, SetDest, iter) << ")" << endl;
}

int main()
{
    //================== Arr + Set
    cout << "Arr + Set" << endl;
    int* ArrSrc = new int[2]{ 1, 2 };
    set<int> SetDest = { 1, 2, 3 };
    printIsProperSubsetOf(ArrSrc, 2, SetDest); // 2, true
    delete[] ArrSrc;
    SetDest.clear();

    ArrSrc = new int[3]{ 1, 2, 3 };
    SetDest = { 1, 2, 3 };
    printIsProperSubsetOf(ArrSrc, 3, SetDest); // 3, false
    delete[] ArrSrc;
    SetDest.clear();

    ArrSrc = new int[3]{ 1, 2, 3 };
    SetDest = { 1, 2};
    printIsProperSubsetOf(ArrSrc, 3, SetDest); // 0, false
    delete[] ArrSrc;
    SetDest.clear();

    ArrSrc = new int[2]{ 2, 3 };
    SetDest = { 1, 2, 3, 4 };
    printIsProperSubsetOf(ArrSrc, 2, SetDest); // 2, true
    delete[] ArrSrc;
    SetDest.clear();

    cout << endl;


    //================== Arr + Arr
    cout << "Arr + Arr" << endl;
    ArrSrc = new int[2]{1, 2};
    int* ArrDest = new int[3]{ 1, 2, 3};
    printIsProperSubsetOf(ArrSrc, 2, ArrDest, 3); // 2, true
    delete[] ArrSrc;
    delete[] ArrDest;

    ArrSrc = new int[3]{ 1, 2, 3};
    ArrDest = new int[3]{ 1, 2, 3};
    printIsProperSubsetOf(ArrSrc, 3, ArrDest, 3); // 3, false
    delete[] ArrSrc;
    delete[] ArrDest;

    ArrSrc = new int[3]{ 1, 2, 3 };
    ArrDest = new int[2]{ 1, 2};
    printIsProperSubsetOf(ArrSrc, 3, ArrDest, 2); // 0, false
    delete[] ArrSrc;
    delete[] ArrDest;

    ArrSrc = new int[2]{ 2, 3 };
    ArrDest = new int[4]{ 1, 2, 3, 4 };
    printIsProperSubsetOf(ArrSrc, 2, ArrDest, 4); // 3, true
    delete[] ArrSrc;
    delete[] ArrDest;
}