이 문제에서는 크기가 각각 m과 n인 두 개의 정수 배열 arr1[]과 arr2[]가 주어집니다. 우리의 과제는 arr2가 arr1의 부분 집합(subset)인지 여부를 판별하는 것입니다.
두 배열 arr1[]과 arr2[]는 정렬되어 있지 않으며(unordered), 모든 요소는 중복 없이 서로 다른 값을 가집니다.
예시를 통해 문제를 이해해 보겠습니다.
입력 : arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1}
출력 : arr2는 arr1의 부분 집합입니다.문제 해결 접근 방식
이 문제는 다양한 방법으로 해결할 수 있습니다. 아래에서 각 방법의 동작 원리와 함께 실제 구현 코드를 살펴보겠습니다.
방법 1: 중첩 반복문을 이용한 직접 비교
가장 기본적인 방법은 부분 집합 여부를 직접 검사하는 것입니다. 중첩 반복문을 사용하여 바깥쪽 반복문은 arr2[]의 각 요소를 순회하고, 안쪽 반복문은 arr1[]의 각 요소를 순회합니다. arr2의 모든 요소가 arr1에 존재하는지 확인하고, 하나라도 존재하지 않으면 false(arr2는 arr1의 부분 집합이 아님)를 반환하며, 모두 존재하면 true(arr2는 arr1의 부분 집합임)를 반환합니다.
예제 코드
#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의 각 요소에 대해 이진 탐색(binary search)을 수행하여 arr1[] 내에 해당 값이 있는지 찾습니다. 만약 찾지 못한 요소가 하나라도 있다면 false를 반환하고, arr2의 모든 요소가 arr1에 존재한다면 true를 반환합니다.
예제 코드
#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[]에 존재하는지 확인합니다. 이때 두 배열의 요소를 가리키는 인덱스를 활용한 투 포인터(two pointer) 방식으로 간단하게 처리할 수 있습니다.
예제 코드
#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: 해싱(Hashing) 활용
네 번째 방법은 해싱을 이용하는 것입니다. arr1의 모든 요소로 해시 테이블(집합)을 생성한 후, arr2의 요소들이 해시 테이블에 존재하는지 검색합니다. 모든 값이 발견되면 true(arr2는 arr1의 부분 집합)를 반환하고, 하나라도 없다면 false(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: set 자료구조 활용
마지막 방법은 set 자료구조를 이용하는 것입니다. 먼저 arr1의 모든 값을 담은 새로운 집합(set)을 만들고 그 크기를 저장합니다. 이후 arr2의 모든 값을 이 집합에 삽입해 보는데, 삽입 후 집합의 크기가 변했다면 arr2에는 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[]
마무리
지금까지 C++에서 한 배열이 다른 배열의 부분 집합인지 확인하는 다섯 가지 방법을 살펴보았습니다. 방법 1은 구현이 간단하지만 O(m×n)의 시간 복잡도를 가지며, 방법 2와 3은 정렬을 활용해 O(m log m + n log n)으로 개선됩니다. 방법 4와 5는 해시 기반 자료구조를 사용하여 평균적으로 더 빠른 성능을 제공하므로, 입력 크기가 클 때 특히 유용합니다. 문제의 조건과 입력 크기에 따라 적절한 방법을 선택하시기 바랍니다.