C++ 중복 없애기 (unique, erase)

 

중복을 없애고 순서대로 만드는 작업은 문제를 풀다보면 많이 사용되는 방법이다.

C++에서 중복을 없애는 방법에 대해서 알아보자.

 

---

unique라는 함수를 사용하게 되면 범위 안의 요소 중에서 앞에서부터 비교해가며 중복되는 요소를 제거하고, 중복되지 않은 것은 그대로 두게 된다.

 

그런데 unique만을 단독적으로 사용하게 되면 원하는 모습을 찾을 수 없다.
아래 예시를 보자.

#include<bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v{5, 5, 6, 6, 7, 3, 3, 2, 1, 1, 2, 2, 3, 4, 5, 8, 7, 8, 7, 9, 9};
    
    auto it = unique(v.begin(), v.end());
    for(int i : v) cout << i << " ";
    
    return 0;
}

// 5 6 7 3 2 1 2 3 4 5 8 7 8 7 9 8 7 8 7 9 9

분명 unique를 사용했다. 

그런데 순서가 이상하고, 연속으로된 중복만 지워졌으며 여전히 중복은 남아있다.

unique는 중복된 값을 컨테이너에서 찾아 제거하는 역할을 하는데, "인접한 요소"를 비교하여 중복 값을 찾고 맨 뒤로 보낸다. 그리고 중복된 값 중 맨 마지막에 위치하는 요소를 반환한다.

 

대부분 이런 경우 높은 순서로, 혹은 낮은 순서로 sorting 작업을 함께 필요로 하는 경우가 많다.

 

그렇다면 어떻게 해야 낮은 것으로부터 높은 것으로 sorting을 하고, 중복을 삭제할 수 있을까?

sort와 erase를 사용할 수 있다.

아래 예시를 보자.

#include<bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v{5, 5, 6, 6, 7, 3, 3, 2, 1, 1, 2, 2, 3, 4, 5, 8, 7, 8, 7, 9, 9};
    
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i : v) cout << i << " ";
    
    return 0;
}

// 1 2 3 4 5 6 7 8 9

이번에는 원하는대로 결과가 나왔다.

추가로 사용된 함수는 sort(), erase() 이다.

우선 낮은 요소부터 높은 요소로 순서를 sorting을 시킨다.

그리고  erase를 사용하는데, 이는 중복된 값을 컨테이너에서 찾아 제거하는 역할을 한다.

unique가 중복된 값을 맨 뒤로 보내는데 반해, erase는 중복된 값 중 맨 뒤에 있는 요소들을 삭제한다.

그렇기 때문에 위와 같이 작성했을 때, 중복된 요소들이 반환되지 않는  것이다.