두 vector의 집합 구하기 (C++)

A+B-A∩B=A∪B 공식을 이용하여 두 vector의 교집합과 합집합을 구할 수 있고, 추가로 부분집합의 여부까지 구할 수 있다.

Set 라이브러리는 많은 프로그래밍 언어에서 지원하고 있으므로 C++가 아니더라도 이 방법을 충분히 이용할 수 있다.

C++의 set에는 중복을 허용하지 않는 set, 중복을 허용하는 multiset을 지원하며, 이들을 이용하여 두 벡터의 합집합과 교집합을 구해볼 것이다.

 

1. 합집합 구하기

- A∪B=A+B-A∩B

- set은 중복 요소가 자동으로 제거되기 때문에 벡터 a, b의 원소를 모두 set에 넣으면 set에 있는 요소들이 합집합이 된다.

 

2. 교집합 구하기

- A∩B=A+B-A∪B

- 중복을 허용하는 multiset에 벡터 a, b의 원소를 모두 저장해두고, 합집합에 있는 요소들을 multiset에서 찾아 하나씩 제거해주면 된다. 이 때, 단순히 erase() 함수를 사용한다면 해당 값을 가지는 모든 요소들을 제거하므로, 하나만을 제거하기 위해서는 iterator을 이용하여 위치를 기반으로 제거해줘야 한다.

 

합집합/교집합 소스코드

 

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main(){
  vector<int> a={1,3,5,7};
  vector<int> b={2,3,4,5,6};
  set<int> union_set; // 합집합
  multiset<int> inter_set; // 교집합

  for(int i=0;i<a.size();i++) {
    union_set.insert(a[i]);
    inter_set.insert(a[i]);
  }

  for(int i=0;i<b.size();i++) {
    union_set.insert(b[i]);
    inter_set.insert(b[i]);
  }

  // 합집합
  cout<<"합집합"<<"\n";
  for(set<int>::iterator uit=union_set.begin(); uit!=union_set.end(); uit++) cout<<*uit<<" ";
  cout<<"\n";
  
  // 교집합
  cout<<"교집합"<<"\n";
  multiset<int>::iterator it;
  for(set<int>::iterator uit=union_set.begin(); uit!=union_set.end(); uit++) {
    it=inter_set.find(*uit); // 삭제할 위치를 지정
    inter_set.erase(it);
  }
  for(multiset<int>::iterator iit=inter_set.begin(); iit!=inter_set.end(); iit++) cout<<*iit<<" ";
}

 

3. 부분집합 여부 구하기

- 벡터 a, b의 합집합과 교집합을 구해 놓았다면 두 벡터가 부분집합 관계인지 구하는 것은 간단하다.

- 벡터 a의 요소의 개수가 교집합의 요소의 개수와 일치하다면 벡터 b는 벡터 a를 포함하고 있다는 뜻이다.

if(a.size()==inter_set.size()) cout<<"a는 b의 부분 집합이다."