반응형
C++ 벡터에서 중복 요소 제거하는 두 가지 방법
{1, 1, 2, 2, 3, 3} 같은 벡터에서 중복을 제거해 1, 2, 3만 남기는 방법을 정리한다. 대표적으로 map을 쓰는 방법과 unique()를 쓰는 방법 두 가지가 있다.
방법 1. map 이용하기
map은 키(key)가 중복될 수 없다는 성질을 가진다. 이를 이용해 각 값을 키로 등록하면 자연스럽게 중복이 걸러진다. 게다가 map은 키 기준으로 자동 정렬되므로 결과도 오름차순으로 나온다.
#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main() {
vector<int> v{1, 1, 2, 2, 3, 3};
for(int i : v){
if(mp[i]){ // 이미 등록된 값이면
continue; // 건너뛴다
}else{
mp[i] = 1; // 처음 보는 값이면 등록
}
}
vector<int> ret;
for(auto it : mp){
ret.push_back(it.first); // 키(값)만 뽑아온다
}
for(int i : ret) cout << i << '\n';
return 0;
}
동작 원리: {1:1}{2:1}{3:1} 형태로 각 값을 키에 한 번씩만 등록 → 키만 추출하면 1, 2, 3이 남는다.
- 장점 : 결과가 자동 정렬됨, 로직이 직관적
- 단점 : map 삽입 비용 때문에 O(n log n), 메모리 추가 사용
방법 2. unique() 이용하기
unique()는 범위 안의 요소를 앞에서부터 서로 비교하며, 인접한 중복을 제거하는 함수다. 시간 복잡도는 O(n)이다.
#include <bits/stdc++.h>
using namespace std;
vector<int> v {2, 2, 1, 1, 2, 2, 3, 3, 5, 6, 7, 8, 9};
int main() {
sort(v.begin(), v.end()); // ★ 반드시 정렬 먼저!
v.erase(unique(v.begin(), v.end()), v.end());
for(int i : v) cout << i << " ";
cout << '\n';
return 0;
}
주의: 반드시 정렬부터!
unique()는 "인접한" 중복만 제거한다. 즉 떨어져 있는 중복은 걸러내지 못한다. 예를 들어 위 예제에서 2 ... 2 ...처럼 값이 흩어져 있으면, 정렬 없이 unique()만 쓸 경우 중복이 그대로 남는다. 그래서 반드시 sort()로 같은 값들을 붙여 놓은 뒤 unique()를 호출해야 한다.
왜 erase까지 필요한가?
unique()는 중복을 실제로 삭제하는 게 아니라, 중복이 제거된 뒤의 "끝 위치(반복자)"를 반환할 뿐이다. 뒤쪽에는 쓰레기 값이 남는다. 따라서 erase()로 그 뒤 구간을 실제로 잘라내야 벡터 크기까지 정리된다.
v.erase( unique(v.begin(), v.end()), v.end() );
// ↑ 새 끝 위치 반환 ↑ 원래 끝
// → 이 사이(쓰레기 값 구간)를 삭제
두 방법 비교
| 기준 | map | sort + unique |
|---|---|---|
| 시간 복잡도 | O(n log n) | O(n log n) (정렬 포함) / unique 자체는 O(n) |
| 정렬 여부 | 자동 정렬됨 | 직접 sort 필요 |
| 추가 메모리 | map 만큼 추가 사용 | 제자리(in-place) 처리 |
| 추천 상황 | 정렬 결과가 함께 필요할 때 | 단순히 중복만 빠르게 제거할 때 |
정리
- 중복 제거의 핵심 두 방법은 map(키 중복 불가)과 sort + unique다.
unique()는 인접 중복만 제거하므로 정렬이 필수 전제다.unique()는 삭제가 아니라 끝 위치만 알려주므로erase()와 짝으로 써야 한다.- 실전에서는 대부분 간결하고 in-place인
sort + unique를 더 많이 쓴다.