23. c++ stl vector 중복 원소 제거 - unique() erase()

  제거 알고리즘은 원소를 실제로 제거하지 않고 논리적으로 제거(다음 원소로 덮어쓰기)하기 때문에 순차열의 size를 실제로는 변경하지 않습니다. 실제 size를 변경하려면 컨테이너의 erase() 멤버 함수를 이용하면 됩니다.

 

알고리즘	설명
p = unique(b, e)	구간 [b, e)의 순차열을 인접한 중복 원소(값이 같은 원소)가 남지 않도록 덮어쓰기로 이동한다. 알고리즘 수행후 순차열은 [b,p)가 된다.
정렬된 상태에서 unique() 알고리즘을 수행한다면 모든 원소를 유일하게 만들 수 있습니다.
예를 들어 ss = [10, 50, 30, 30, 40, 50] 라면 정렬 후 ss= [10, 30, 30, 40, 50 ,50]이 됩니다. unique() 수행 후  ss = [10, 30, 40, 50, 50 50]이 됩니다.

 

[ vector에서 중복된 원소 제거하기 소스 ]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() 
{
	vector <int> ss;
	ss.push_back(10);
	ss.push_back(50);
	ss.push_back(20);
	ss.push_back(30);
	ss.push_back(40);
	ss.push_back(50);
	ss.push_back(30);
	ss.push_back(40);
	ss.push_back(20);
	ss.push_back(30);
	ss.push_back(20);
	ss.push_back(50);	
	
	sort(ss.begin(), ss.end());
	ss.erase(unique(ss.begin(), ss.end()), ss.end());
	
	for(int i=0;i<ss.size();i++)
	{
		cout << ss[i] << ' ';
	}

	return 0;
}

 

[ 입력데이터 값 압축하기 ]

문제를 풀다보면 입력데이터 값 자체가 너무 커서 곤란한 경우가 있습니다.

이럴 경우 입력데이터를 1부터 n까지 차례대로 재 설정해주고 문제를 풀면 더 쉽게 풀수 있겠죠? 

아래 소스를 입력해보세요

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main() 
{
	vector <int> b(10); 
	vector <int> ss;
	ss.push_back(100);
	ss.push_back(60000);
	ss.push_back(20);
	ss.push_back(3);
	ss.push_back(598);
	ss.push_back(54);
	ss.push_back(957);
	ss.push_back(10);
	ss.push_back(540);
	ss.push_back(78);
	
	for(int i=0;i<10;i++)
	{
		b[i] = ss[i];
	}
	
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());

	map <int, int> d;
	
	for(int i=0;i<b.size();i++)
	{
		d[b[i]] = i+1;
	}
	for(int i=0;i<10;i++)
	{
		ss[i] = d[ss[i]];
	}
	
	for(int i=0;i<10;i++)
	{
		cout << ss[i] << ' ';
	}
	
	return 0;
}