unique
in Tips. / 🚩 C++ 팁 목록 (12)
벡터의 중복 원소를 제거할 때 쓰는 unique
벡터의 중복 원소를 제거하고 싶을 때 “algorithm” 헤더에 있는 unique를 쓰면 편리합니다!
unique는 연속되는 중복 원소가 있으면 처음에 나온 원소를 제외한 나머지를 제거합니다.
예를 들어서 벡터에 1 1 3 2 2 4 3 1 이 들어있으면 1 3 2 4 3 1 ? ? 으로 만듭니다.
1과 2를 지우면서 생긴 빈자리는 의미없는(undefined) 값으로 채워지고 쓰레기 값이 처음 나오는 위치의 이터레이터를 리턴합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {1,1,3,2,2,4,3,1};
vector<int>::iterator it = unique(v.begin(),v.end());
cout << v.size() << '\n' // 8;
for(auto i = v.begin(); i != it; i++)
cout << *i << " "; // 1 3 2 4 3 1
}
벡터의 모든 중복 원소를 지우고 싶을 때는 벡터를 sort 한 뒤에 unique를 해주시면 됩니다.
1 1 3 2 2 4 3 1 을 정렬하면 1 1 1 2 2 3 3 4 로 같은 값은 모두 연속하게 됩니다.
이 때 unique를 해주면 1 2 3 4 ? ? ? ? 로 중복되는 값이 모두 제거됩니다.
뒤에 있는 의미없는 값인 ?을 지울 때는 erase함수를 씁니다.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {1,1,3,2,2,4,3,1};
sort(v.begin(), v.end());
vector<int>::iterator it = unique(v.begin(),v.end());
v.erase(it,v.end());
for(int i=0; i<v.size(); i++)
cout << v[i] << " "; // 1 2 3 4
}
unique - erase의 시간복잡도는 O(n)이며, 좌표압축을 할 때 유용하게 사용됩니다.
