set처럼 vector에서도 중복된 것들 없애기, unique()

https://www.acmicpc.net/problem/1181

물론 set으로 중복된 것을 없애면서 정렬까지 가능하나.

벡터에서도 필요한 것만 하기 위해서 중복된 것을 없애는 작업을 알아보자

 

위 문제가 좋은 문제다.

 

#include<algorithm>를 해줘야 쓸 수 있다.

 

쉽게 말하자면 값이 같고 뭉쳐있는 그룹은 리더가 대표하겠다

라고 생각하면된다. 값이 같아도 그룹이 나누어져 있으면 각 그룹의 대표를 가져오겠다는 말이다.

**반환은 역시나 iterator를 반환한다.

 

 

 

 

 

#예1 (정렬 x)

// unique algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::unique, std::distance
#include <vector>       // std::vector

bool myfunction (int i, int j) {
  return (i==j);
}

int main () {
  int myints[] = {10,20,20,20,30,30,20,20,10};           // 10 20 20 20 30 30 20 20 10
  std::vector<int> myvector (myints,myints+9);

  // using default comparison:
  std::vector<int>::iterator it;
  it = std::unique (myvector.begin(), myvector.end());   // 10 20 30 20 10 ?  ?  ?  ?
                                                         //                ^

  myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30 20 10

  // using predicate comparison:
  std::unique (myvector.begin(), myvector.end(), myfunction);   // (no changes)

  // print out content:
  std::cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

** 기존 벡터의 빈 공간이 생김

resize()를 해도 됨.

resize로 현재 unique로 반환된 iterator까지의 크기로 벡터를 다시 만들어도 된다.

 

 

#예2 (오름차순 정렬)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector <int> v;
	v.push_back(1); v.push_back(1);
	v.push_back(2);
	v.push_back(3); v.push_back(3);
	v.push_back(4);
	v.push_back(5); v.push_back(5); v.push_back(5);
	v.push_back(6);

	for (const auto& n : v) cout << n << ' ';	 //      1 1 2 3 3 4 5 5 5 6
	cout << endl;


	unique(v.begin(), v.end());                 //연속되는 같은 값들은 하나만 남긴다.
    
	for (const auto& n : v) cout << n << ' ';   // 1 2 3 4 5 6
	cout << endl;
	
	return 0;
}

 

 

즉 unique함수는 그대로 iterator를 돌면서 수행하기 때문에

정렬하고 수행하면 그 원소는 유일해지겠지만

정렬하지 않고 수행하면 뭉쳐있는대로 수행된다.

 

 

즉, 정렬 하지 않은 것과 한 것의 차이가 많이 나므로

문제에 따라서 정렬을 할 지 생각하고 unique 함수를 돌릴 수 있도록 해야 한다.

 

 

 

*** 하지만 우리는 일반적으로 erase와 같이 쓴다.

왜냐면 erase를 하지 않으면 반환된 vector에 빈 공간이 생기기 때문이다.

때문에 unique로 만들어진 빈 공간, 즉 기존의 vector의 end까지 생긴 공간을 erase가 지워줘야 한다.

 

**unique가 반환한 iterator는 unique가 만들어진 마지막 값을 가리키고 있다.

v.erase(v.begin()+s, v.begin()+e) 명령어를 입력하면 [s,e) 원소가 삭제된다. 즉 시작 지점은 닫힌구간, 끝나는 지점은 열린 구간으로 삭제된다.

즉, 반환한 iterator 부터 기존 벡터의 끝까지 다 erase시켜주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector <int> v;
	v.push_back(1); v.push_back(1);
	v.push_back(2);
	v.push_back(3); v.push_back(3);
	v.push_back(4);
	v.push_back(5); v.push_back(5); v.push_back(5);
	v.push_back(6);

	for (const auto& n : v) cout << n << ' ';	 //      1 1 2 3 3 4 5 5 5 6
	cout << endl;

	//erase와 unique를 같이 씀.unique를 돌면서
	v.erase(unique(v.begin(), v.end()), v.end());   
    
	for (const auto& n : v) cout << n << ' ';   // 1 2 3 4 5 6
	cout << endl;
	
	return 0;
}

 

 

unique()의 시간 복잡도는 O(N)이다.