배열이 다른 배열의 하위 집합인지 여부 찾기 - C++에서 방법 3 추가

이 문제에서는 크기가 m 및 n인 정수 arr1[] 및 arr2[]의 두 배열이 제공됩니다. 우리의 임무는 배열이 다른 배열의 하위 집합인지 여부를 찾는 것입니다 - 방법 3 추가 .

arr1[] 및 arr2[] 배열은 모두 순서가 없고 고유한 요소가 있습니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1}
Output : arr2 is a subset of arr1.

솔루션 접근 방식

이 문제를 해결하기 위해 여기에서 여러 가지 방법을 논의했습니다. 프로그램을 통해 각각의 작업을 살펴보겠습니다.

방법 1

문제를 해결하는 한 가지 방법은 하위 집합을 직접 확인하는 것입니다. 이것은 배열 arr2[]의 각 요소에 대해 외부 루프를 사용하고 배열 arr1[]의 각 요소에 대해 내부 루프를 사용하여 수행됩니다. arr2의 각 요소가 arr1에 있는지 확인하고, 1을 반환하면( arr2는 arr1의 하위 배열) 그렇지 않으면 0을 반환합니다(arr2는 1의 하위 배열이 아님).

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
   int j = 0;
   for (int i = 0; i < n; i++) {
      for (j = 0; j < m; j++) {
         if (arr2[i] == arr1[j])
            break;
      }
      if (j == m)
         return false;
   }
   return true;
}
int main(){
   int arr1[] = {5, 2, 1, 6, 8, 10};
   int arr2[] = {6, 2, 1};
   int m = sizeof(arr1) / sizeof(arr1[0]);
   int n = sizeof(arr2) / sizeof(arr2[0]);
   isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a  subset of arr1[]";
   return 0;
}

출력

arr2[] is subset of arr1[]

방법 2

문제를 해결하는 또 다른 방법은 arr2의 모든 요소가 arr1에 있는지 확인하는 것입니다. 이를 효과적으로 수행하기 위해 배열 arr1[]을 정렬한 다음 arr2의 각 요소에 대해 이진 검색을 수행하여 arr1[]에서 arr2[]의 요소를 검색합니다. 이제 요소가 발견되지 않으면 0을 반환하고(arr2는 arr1의 하위 배열이 아님) arr2의 모든 요소가 arr1에 있으면 1을 반환합니다(arr2는 arr1의 하위 배열임).

예시

솔루션 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int low, int high, int x){
   if (high >= low){
      int mid = (low + high) / 2;
      if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
         return mid;
      else if (x > arr[mid])
         return binarySearch(arr, (mid + 1), high, x);
      else
         return binarySearch(arr, low, (mid - 1), x);
   }
   return -1;
}
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
   int i = 0;
   sort(arr1, arr1 + m);
   for (i = 0; i < n; i++) {
      if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
         return 0;
   }
   return 1;
}
int main(){
   int arr1[] = {5, 2, 1, 6, 8, 10};
   int arr2[] = {6, 2, 1};
   int m = sizeof(arr1) / sizeof(arr1[0]);
   int n = sizeof(arr2) / sizeof(arr2[0]);
   isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
   return 0;
}

출력

arr2[] is subset of arr1[]

방법 3

솔루션을 찾는 또 다른 방법은 먼저 배열 arr1[] 및 arr2[]를 모두 정렬하는 것입니다. 그런 다음 배열 arr2[]의 모든 요소에 대해 해당 요소가 arr1[]에 있는지 확인합니다. 이를 위해 두 배열의 요소 인덱스를 사용하는 직접적인 방법이 있습니다.

예시

솔루션 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
   int i = 0, j = 0;
   if (m < n)
      return 0;
   sort(arr1, arr1 + m);
   sort(arr2, arr2 + n);
   while (i < n && j < m){
      if (arr1[j] < arr2[i])
         j++;
      else if (arr1[j] == arr2[i]){
         j++;
         i++;
      }
      else if (arr1[j] > arr2[i])
         return 0;
   }
   return (i < n) ? false : true;
}
int main()
{
   int arr1[] = {5, 2, 1, 6, 8, 10};
   int arr2[] = {6, 2, 1};
   int m = sizeof(arr1) / sizeof(arr1[0]);
   int n = sizeof(arr2) / sizeof(arr2[0]);
   isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
   return 0;
}

출력

arr2[] is subset of arr1[]

방법 4

또 다른 방법은 arr2가 arr1의 하위 집합인지 확인하기 위해 해싱을 사용하는 것입니다. . 우리는 arr1의 모든 요소를 ​​사용하여 해시 테이블을 만든 다음 해시 테이블에서 arr2의 요소를 검색합니다. 값이 발견되면 1(arr2는 arr1의 하위 집합)을 반환하고 그렇지 않으면 0(arr2는 arr1의 하위 집합이 아님)을 반환합니다.

예시

솔루션 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
   set<int> arr1Hash;
   for (int i = 0; i < m; i++)
      arr1Hash.insert(arr1[i]);
   for (int i = 0; i < n; i++) {
      if (arr1Hash.find(arr2[i]) == arr1Hash.end())
         return false;
   }
   return true;
}
int main(){
   int arr1[] = {5, 2, 1, 6, 8, 10};
   int arr2[] = {6, 2, 1};
   int m = sizeof(arr1) / sizeof(arr1[0]);
   int n = sizeof(arr2) / sizeof(arr2[0]);
   isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
   return 0;
}

출력

arr2[] is subset of arr1[]

방법 5

문제를 해결하는 또 다른 방법은 데이터 구조 설정을 사용하는 것입니다. . 모든 값이 arr1인 새 집합을 만들고 길이를 확인합니다. 그런 다음 추가로 길이가 변경되면 arr2는 arr1의 하위 집합이 아닌 모든 값을 삽입하려고 합니다. arr2의 요소를 추가한 후 길이에 변화가 없으면 arr2는 arr1의 하위 집합입니다.

예시

솔루션 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
   unordered_set<int> arrSet;
   for (int i = 0; i < m; i++) {
      arrSet.insert(arr1[i]);
   }
   int setSize = arrSet.size();
   for (int i = 0; i < n; i++) {
      arrSet.insert(arr2[i]);
   }
   if (arrSet.size() == setSize) {
      return true;
   }
   else {
      return false;
   }
}
int main(){
   int arr1[] = {5, 2, 1, 6, 8, 10};
   int arr2[] = {6, 2, 1};
   int m = sizeof(arr1) / sizeof(arr1[0]);
   int n = sizeof(arr2) / sizeof(arr2[0]);
   isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
   return 0;
}

출력

arr2[] is subset of arr1[]