vector 중복 제거

검색하면 다 나오는 것이지만, 나중에 보기위해 블로그에 끄적끄적

 

코딩 문제를 풀다가 나온 문제 중 하나가 연속해서 같은 숫자가 나오면 제거하는 문제였다.

 

예를 들면 { 1, 1, 2, 3, 4, 4, 4, 5 } 로 나오면 답은 { 1, 2, 3, 4, 5 } 가 되는 것이다.

 

처음에는 vector가 나오면 항상 쓰는 방식인 iterator 로 풀었다.

 

for(it = arr.begin(); it != arr.end()-1;)

{

    if(*it == *(it+1))

    {

        it = arr.erase(it);

    }

    else

    {

        ++it;

    }

}

 

답은 다 맞는데, 효율성이 안좋다고 나왔다.

 

그래서 검색해보았다.

 

대학때 배운걸 생각해보면 분명 vector에서 중복제거하는 함수가 있었다.

 

역시나 사람들이 잘 정리한 글들이 있었다.

 

만능 algorithm header를 넣고, unique 함수를 이용하면 된다는 것이었다.

 

unique는 중복된 원소들을 vector의 맨 마지막에 밀어넣는 함수다.

 

그리고 중복되지 않은 원소 중 마지막 원소의 다음 위치를 리턴해준다.

 

즉, 위에 있는 { 1, 1, 2, 3, 4, 4, 4, 5 } 를 예로 들면 {1, 2, 3, 4, 5, 1, 4, 4, 4 } 로 만들고, 5번째 원소 다음을 리턴해준다.

 

그래서 erase와 섞어서 뒤에 있는 원소들을 없애버리면 중복되지 않는 원소들만 남는다.

 

그러면 arr.erase(unique(arr.begin(), arr.end()), arr.end()); 로 한줄코드가 된다.

 

효율성 체크도 잘 넘어간다.

 

http://blog.naver.com/PostView.nhn?blogId=withham1&logNo=221102099316

[C++] unique 함수를 이용한 vector 중복 제거

 

뒤늦게 찾았지만, 이 분의 블로그 글이 잘 설명되어있다.