C++ vector 중복 원소 삭제

 

1. unique 함수

unique 함수는 vector에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수 (algorithm 헤더에 정의)

자신이 바꾼 vector의 end()를 반환 (중복 원소들(쓰레기 값들)의 첫 번째 위치 리턴)

 

unique 함수는 앞과 뒤의 원소들을 비교하기 때문에 반드시 정렬을 한 뒤 실행

unique 함수는 erase 함수에 중첩하여 사용 가능

 

사용 순서

1. sort

벡터를 정렬한다.

 

2. unique

중복 원소는 벡터의 제일 뒷부분(쓰레기 값)으로 보낸다.

 

3. erase

중복된 원소들이 있는 뒷 부분을 삭제한다.

 

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

int main() {
	vector<int> v;

	v.push_back(1);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(2);
	v.push_back(1);
	v.push_back(5);

	cout << "Original Vector: ";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << "\n\n";

	sort(v.begin(), v.end());

	cout << "Sorted Vector: ";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << "\n\n";

	v.erase(unique(v.begin(), v.end()), v.end());

	cout << "unique + erase: ";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << "\n\n";

}

 

 

 

---

2. set + assign 함수

set은 중복 원소를 허용하지 않는 컨테이너이다.

원소를 set에 삽입한 후 set의 원소들을 vector에 assign한다.

 

vector<vector<T>> 등 복잡한 벡터의 중복 원소 제거에 사용 가능

 

사용 순서

1. set에 원소 삽입

 

2. vector에 assign

 

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

int main() {
	set<int> s = { 1,1,2,3,2,4,5,1 };

	cout << "Set: ";
	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << "\n\n";

	vector<int> v;
	v.assign(s.begin(), s.end());

	cout << "Vector: ";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << "\n\n";
}

 

---

 

응용

벡터를 담은 벡터에서 중복되지 않는 벡터 개수 구하기 (백준 13915)

 

        vector<vector<int>> v;
        
        set<vector<int>> s;
        for (int i = 0; i < N; i++) {
            s.insert(v[i]);
        }
        
        cout << s.size() << endl;