[10주 완성 C++ 코딩테스트] 필수개념 - map, unique()

코딩테스트에서 중복없는 값을 출력하라고 할 때, map 이나 unique 함수를 이용한다.

 

1. map

#include <iostream>
#include <map>
#include <vector>
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);
	}
	for (int i : ret) cout << i << '\n';
}

 

2. unique()

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

vector<int> v;

int main() {
	for (int i = 1; i <= 5; i++){
		v.push_back(i);
		v.push_back(i);
	}
	for (int i : v) cout << i << " ";
	cout << '\n';

	// 중복되지 않은 요소로 채운 후, 그 다음 이터레이터를 반환한다.
	auto it = unique(v.begin(), v.end());
	cout << it - v.begin() << '\n';

	// 앞에서 부터 중복되지 않게 채운 후 나머지 요소들은 그대로 둔다.
	for (int i : v) cout << i << " ";
	cout << '\n';

	//unique()의 iterator에서 벡터 끝까지를 erase()로 지워주면 된다.
	v.erase(it, v.end());
	for (int i : v) cout << i << " ";
	cout << '\n';

	return 0;
}

1 1 2 2 3 3 4 4 5 5
5
1 2 3 4 5 3 4 4 5 5
1 2 3 4 5

 

* unique(): 범위 안에 요소 중 연속된 요소를 지우고 나머지 요소들은 삭제하지 않고 그대로 두는 함수.

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

 

즉, unique() 로 중복된 요소를 찾아서 정렬하고 찾은곳 뒤부터 끝까지를 erase() 하면 중복된 요소가 제거된다.

이 때, 나머지 요소들은 삭제하지 않고 그대로 두기 때문에 sort() 를 먼저 하고 하면 중복된 수를 모두 제거한 배열이 나온다.

---

* hash map 참고 문제 및 활용예시

https://i-believe-in-me.tistory.com/224

[C++][Programmers][해시] 포켓몬

포켓몬을 2/n 개 선택했을 때, 선택할 수 있는 포켓몬 종류의 최대값을 구해야 하므로 포켓몬 종류별로 count 할 hash map이 필요하다.

 

* unique(), erase() 참고 문제 및 활용예시

https://i-believe-in-me.tistory.com/229

[C++][Programmers][스택/큐] 같은 숫자는 싫어

단순히 연속된 숫자를 지우면 되는 문제이므로 unique(), erase() 함수를 이용하면 된다.