[알고리즘/C++] 중복된 요소 제거하는 방법

중복된 요소를 제거하는 방법은 두가지가 있다.

1. map을 사용해 key값들만 뽑아주기

2. unique() 사용하기

 

 

1. map을 사용해 key값들만 뽑아주기

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
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';
}

 

 

2. unique() 사용하기

unique()란?

: vector와 배열에서 범위내에 맨 앞부터 순서대로 서로를 비교해가며 중복되는 요소를 제거해주는 함수

모두 제거가 되었으면 나머지 부분은 그대로 둔다.

O(n)의 시간 복잡도를 가진다.

 

예시

vector<int> v = {1,1,2,2,3,3,4,4,5,5};
auto it = unique(v.begin(), v.end());

 

위와 같은 벡터에서 unique함수를 통해 중복된 문자를 제거해주면 벡터가 다음과 같이 된다.

{1,2,3,4,5,3,4,4,5,5}

 

중복되는 숫자를 전부 하나씩만 쓴 후에 남은 자리는 그대로 가져오기 때문에 3,4,4,5,5가 들어가 있는 것을 볼 수 있다.

이때 unique의 return 값은 중복된 수를 다 정리한 후 그 다음 이터레이터이다. v[4]까지가 중복된 수 였으므로 it에는 v[5]의 주소가 들어간다.

 

unique()는 바로 앞뒤의 원소들을 비교하기때문에 정렬을 해줘야 올바른 결과가 나온다.

그러므로 sort를 통해 정렬을 해주는 것이 필수이다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	vector<int> v{ 4,3,3,2,4,1,3,5,1,3,4,2,5 };
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()),v.end());
	for (int i : v) cout << i << '\n';
	return 0;
}
/*
출력
1
2
3
4
5
*/

 

위 코드에서 sort를 통해 벡터를 정렬해주고,

erase통해 뒷부분을 날려주었다.

erase는 시작부분부터 끝부분 전 까지 없애주는 메서드인데, unique()가 중복이 제거된 다음의 이터레이터를 반환하므로 제거된 이후부터 끝까지 없어지는 것이다.

그래서 1,2,3,4,5만 뽑아낼 수 있다.