C++에서 중복된 요소 제거하는 법

map

v 값을 map의 key 값에 저장하고 value 값에 중복 유무를 검사하는 boolean 값을 저장합니다.

#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 << " ";
}

1 2 3

 

unique()

범위 안에 있는 요소 중 앞에서부터 서로 비교하여 중복 요소를 제거하고 나머지 요소를 그대로 두는 함수

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

#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
    for(int i=1 ; i<=5 ; i++) {
        v.push_back(i);
        v.push_back(i);
    }

    for(int i : v) cout << i << " ";
    cout << '\n';                                          // 중복되지 않은 요소로 채운 후, 그 다음 iterator를 반환

    auto it = unique(v.begin(), v.end());
    cout << it - v.begin() << '\n';              // 앞에서부터 중복되지 않게 채운 후 나머지 요소들은 그대로 둠

    for(int i : v) cout << i << " ";
    cout << '\n';
    return 0;
}

1 1 2 2 3 3 4 4 5 5
5
1 2 3 4 5 3 4 4 5 5

 

unique()을 쓸 경우 꼭 sort() 와 함께 사용해야 합니다.

 

erase 통해 unique() 처리 이후 나머지 값들을 삭제합니다.

#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;
}

1 2 3 5 6 7 8 9