unique()

배열 중에서 아래와 같은 배열이 있다.

[1, 1, 2, 2, 3, 3]

그럼 이 중에서 중복된 것들을 삭제하는 것은 어떻게 할까?

 

첫번째 방법은 map이다.

간단하게 map을 사용해서 할 수 있다.

map에 1이라는 key를 넣고 value를 할당한다.

그러면 다음 1은 continue 할수가 있고 이런 식으로 하나의 map에 중복된 것들을 삭제하고 오름차순으로 나열 할 수 있다.

 

그럼 코드로 한 번 확인해보자.

#include <iostream>
#include <vector>
#include <map>

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);			// first는 key이다.
    }
    
    for(int i : ret)
        cout << i << '\n';
}

 

 

결과가 잘 나온 것을 확인할 수 있다.

 

두번째 방법은 unique다

 

unique는 범위 안에 있는 요소 중 앞에서부터 서로를 비교해가며 중복되는 요소를 제거,

그리고 나머지 요소들을 삭제하지 않고 그대로 두는 함수이다.

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

 

이제 unique를 사용한 코드를 살펴보자.

 

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

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 << " ";
    
    return 0;
}

 

여기서 보면 우리가 원하는 결과값은 [1, 2, 3, 5, 6, 7, 8, 9]이다.

 

중복된 것들은 삭제하고 오름차순으로 나열하기.

 

그렇다면 일단 여기서 문제점은 정렬을 안하고 unique를 사용하게 되면 결과값은 이렇게 나온다.

[2, 1, 2, 3, 5, 6, 7, 8, 9]

 

unique라는 것은 그림을 보면 이런 식으로 삭제한다.

 

첫번째 인덱스부터 시작해 중복을 비교한다.

이 때 중복이다면 삭제하고 다음것을 비교합니다.

그러면 2와 1을 서로 검사하게 되는데 중복이 아니니 삭제를 진행하지 않는다.

 

그렇기에 [2, 1, 2, 3, 5, 6, 7, 8, 9]라는 결과가 나온 것이다.

전체를 검사한다는 것은 포괄적으로 생각하면 맞지만

실제 검사는 하나 하나 씩 검사하기 때문이다.

 

그렇기에 다시 코드를 보자면

 

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

 

먼저 정렬을 진행한 후에 unique를 진행하는데

unique를 진행하게 되면 중복된 것을 삭제하고 그에 맞는 값을 넣어주는데 이게 다 끝나면 중복 삭제하고 삽입된 값들의 마지막 다음 인덱스를 반환한다.

이게 무슨 말이냐면

 

이런 식이다.

정렬된 것 삭제하고 값을 바꾼 뒤에 중복된 것들을 다 삭제하고 마지막 부분을 반환한다

그래서

 

v.erase(unique(v.begin(), v.end()), v.end());

이런식으로 삭제를 해야한다.

erase는 from - to (어디서부터 ~ 어디까지) 삭제한다.

라는 뜻이다.

 

오늘은 여기까지