중복된 요소를 제거하는 방법
Algorithm Theory
중복된 요소를 제거하는 방법
map
C++ 의 map 은 C# 의 SortedDictionary 와 가장 비슷하다.
map 은 키 값을 기준으로 항상 정렬되어 있다.
map 은 내부적으로 pair 컨테이너로 되어있고, 레드-블랙 트리를 기반으로 구현되어 있다.
검색, 삽입, 삭제 연산이 O(log N) 으로 동작한다.
만약 1, 1, 2, 2, 3, 3 원소를 가지고 있는 배열이 있다.
여기서 중복된 원소를 제거하고 1, 2, 3 으로 뽑아내고싶다면 아래와 같이 작성할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main()
{
map<int, int> mp;
vector<int> vec{1, 1, 2, 2, 3, 3};
for (int i : vec)
{
if (mp[i] != 0) // 이미 key 가 존재한다면 skip
{
continue;
}
else // 처음들어온 key 라면, value 에 1 대입.
mp[i] = 1;
}
vector<int> ret;
for (auto it : mp)
{
ret.push_back(it.first); // ret 배열에 key 값 대입
}
for (int i : ret)
cout << i << '\n';
return 0;
}
1
2
3
1
2
3
Unique ( )
unique 는 범위 안의 요소 중 앞에서부터 서로를 비교해가며 중복되는 요소를 제거하고
나머지 요소들은 삭제하지 않고 그대로 두는 함수이다.
O(n) 의 시간복잡도를 가진다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main()
{
/***************** version 1 ***************/
vector<int> s{4, 3, 3, 5, 1, 2, 3};
s.erase(unique(s.begin(), s.end()), s.end());
for (int i : s)
cout << i << " ";
cout << '\n';
/***************** version 2 ***************/
vector<int> s2{4, 3, 3, 5, 1, 2, 3};
sort(s2.begin(), s2.end());
s2.erase(unique(s2.begin(), s2.end()), s2.end());
for (int i : s2)
cout << i << " ";
return 0;
}
1
2
4 3 5 1 2 3
1 2 3 4 5
iterator
1
s2.erase(unique(s.begin(), s.end()), s.end());
unique 함수의 반환 값은 중복없이 나열된 마지막 원소 다음의 반복자다.
쉽게 말해서 unique 함수가 실행 된 후엔, 반복자를 쓰레기 값이 있는 곳에 위치된다.
s2 vector 같은 경우엔 sort 를 이용하여 오름차순으로 정렬했다.
그럼 아래와 같은 순서를 가지게 된다.
1
1 2 3 3 3 4 5
이 상태에서 unique 함수를 적용하면 아래와 같이 된다.
1
1 2 3 4 5 '4' 5
이와 동시에 '4' 위치에 반복자를 반환하게 된다.
최종적으로 s2[5] ~ s2.end() 사이의 원소들을 erase 함수를 통해 제거한다.