C++ unique : 중복을 제거한다

벡터에서 중복 원소를 제거할 필요가 있을때

algorithm 헤더의 unique 함수를 사용하면 쉽게 제거할 수 있다

unique 함수란?

• 벡터 배열에서 중복되지 않은 원소들을 앞에서부터 채워나가는 함수
• parameter로 range, 시작지점과 종료지점을 받음
• algorithm 헤더에 존재한다

• 중복되지 않은 원소들을 앞에서부터 채워나가는 역할을 하기 때문에,

  중복 원소들은 그대로 벡터 뒷부분에 존재함

주의사항

• 정렬되어있지 않으면 사용할 수 없다
  • 오름차순, 내림차순이던 상관없음. 일단 정렬이 되어있어야함
• 배열의 사이즈는 변하지 않는다
  • 이후 erase나 resize를 통해 쓰레기값을 처리해야함
• 정렬하지 않고 사용하는 경우, 원본값이 손상될 수 있다!

작동 과정

• first와 last iterator를 받아 작동 시작

  template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last)
  {
  if (first==last) return last;
  
  ForwardIterator result = first;
  while (++first != last)
  {
    if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
      *(++result)=*first;
  }
  return ++result;
  } //출처 : https://www.cplusplus.com/reference/algorithm/unique/
  

• 간단히 요약하면, first를 옮겨가며 result와 비교하며 같으면 패스,

  다르면 result에 first 값을 덮어씌운다

• 그러므로 정렬되어있어야 사용이 가능함

• vector의 쓰레기 값의 첫번째 위치가 반환됨.

• 이를 이용해 바로 erase를 사용하여, 이 지점과 벡터의 끝을 지정하면 깔끔하게 제거 가능함

v.erase(v.unique(v.begin(), v.end()), v.end()); 이렇게 사용함

예시

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

using namespace std;

vector<int> s;

int main() {
	
	s.push_back(1);
	s.push_back(2);
	s.push_back(1);
	s.push_back(3);
	s.push_back(2);
	s.push_back(1);
	s.push_back(2);

    // ================================================================
	printf("1. 기본 백터s\n");
	for (int i = 0; i < s.size(); i++)
		cout << s[i] << " ";
	printf("\n\n");
	// 1 2 1 3 2 1 2 
    
    // ================================================================
	printf("2. 미정렬시 unique만 적용한 벡터\n");
	unique(s.begin(), s.end());
	for (int i = 0; i < s.size(); i++)
		cout << s[i] << " ";
	printf("\n\n");
    /* 주의!!!
	정렬하지 않고 사용하는 경우, 원본값이 손상될 수 있다! 
	여기서는 first와 result가 모두 달라 값이 변하지 않았음.
	*/
	// 1 2 1 3 2 1 2 

    // ================================================================
	sort(s.begin(), s.end(), less<>()); // 오름차순으로 정렬
	vector<int> s2 = s; 

	printf("3. 정렬 후 unique 적용한 벡터\n");
	unique(s.begin(), s.end());
	for (int i = 0; i < s.size(); i++)
		cout << s[i] << " ";
	printf("\n\n");
	// 1 2 3 2 2 2 3 
	/*
	배열의 사이즈는 변하지 않고, 앞쪽에 1, 2, 3이 뒷쪽에 쓰레기값이 저장됨
	*/

    // ================================================================
	s2.erase(unique(s2.begin(), s2.end()), s2.end()); 
    // unique는 쓰레기값의 첫 지점을 리턴하므로 이를 erase의 시작지점 매개변수로 넘겨줌 
	printf("4. Unique + erase 까지 적용한 벡터\n");
	for (int i = 0; i < s2.size(); i++)
		cout << s2[i] << " ";
	printf("\n\n");
    // 1 2 3

	return 0;
}

응용

200,000개의 입력이 있을 때,

이 중, 두 원소를 뽑아서 만든 합의 최대값을 찾기

1. 중복 원소를 제거하지 않고, 일일히 조합을 만들어 계산하는 경우

• 20만개에서 2개를 뽑는 조합의 수는

200000C2 = 200,000 * 199,999 / 2 = 약 2백억개

1초에 약 1억번이라고 생각하면 된다

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <time.h>

using namespace std;

#define MAX 200000

int main() {
	clock_t start, finish;
	double duration;

	start = clock();

	vector<int> v;
	for (int i = 0; i < MAX; i++) {
		v.push_back(rand() % 101);
	}

	// next_permuation 연산 수행을 위해서 sort
	sort(v.begin(), v.end());


	int max_val = 0;
	do {
		int sum = 0;
		sum = v[0] + v[1];
		if (max_val < sum) {
			max_val = sum;
		}

		reverse(v.begin() + 2, v.end());

	} while (next_permutation(v.begin(), v.end()));
	cout << max_val << endl;

	finish = clock();

	duration = (double)(finish - start);
	cout << duration << "ms";

	return 0;
}

약 30초 소요. i5-8세대라 역시 다르다

1. 중복원소를 제거하고, 조합 만들어서 계산하는 경우

• 두 원소를 뽑아서 만든 합은 중복을 제거해도 상관없음
  • [1,1,2,3]에서 첫번째 1,3의 합이나, 두번째 1,3의 합이나 중복 연산임

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <time.h>

using namespace std;

#define MAX 200000

int main() {
	clock_t start, finish;
	double duration;

	start = clock();

	vector<int> v;
	for (int i = 0; i < MAX; i++) {
		v.push_back(rand() % 101);
	}

	// next_permuation, unique 연산 수행을 위해서 sort
	sort(v.begin(), v.end());

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

	int max_val = 0;
	do {
		int sum = 0;
		sum = v[0] + v[1];
		if (max_val < sum) {
			max_val = sum;
		}

		reverse(v.begin() + 2, v.end());

	} while (next_permutation(v.begin(), v.end()));
	cout << max_val << endl;

	finish = clock();

	duration = (double)(finish - start);
	cout << duration << "ms";

	return 0;
}

1초도 안걸린다

---

아니면 입력 단계에서 컷 해버리는 방법도 있다

set 컨테이너와 같이, 중복을 허용하지 않는 컨테이너를 사용하면 됨