<map> 자료구조

*헤더로 <map> 을 갖는다. 

 

<map>은 key 와 value 의 쌍으로 이루어진 균형 이진 트리이다. key 를 기준으로 사전순으로 정렬되어 있기 때문에 검색 속도가 빠르다. 바로 map 의 쓰임을 알아보자. 

 

string s= "my name is my name" 

 

스트링 s 에는 "나의 이름은 나의 이름" 이라는 영어 문장을 적었는데 해당 문자열의 알파벳 종류에 따른 개수를 구조화 시키고 싶을 때 <map> 이라는 자료구조를 쓰면 된다. 

 

즉, m 이라는 알파벳이 몇개가 나왔는지 알고 싶다면 map 을 활용 하면 된다.

 

map 은 여러 타입을 묶음으로 가질 수 있으니 사용자는 문제에 맞는 구조로 구현 하면 된다. 

 

map < string, char> 변수명  

map< char, int > 변수명 

map < int, int > 변수명  ..등

 

 

"MYNAM" 이라는 문자열을 <map> 을 사용했다면 다음과 같이 구조가 만들어진다. 

 

이어지는 코드는 "my name is my name" 이라는 문자열을 가지고 <map> 을 적용한 코드다. 그림을 보면서 맵의 구조를 확인하고 어떻게 사용하는지 바로 연습하자. 

#include <map>
#include <iostream>

using namespace std; 

int main() {
	map < char, int> m1; 
	
	string s = "my name is my name"; 
	for (char c : s)m1[c]++; 
	for (auto it = m1.begin(); it != m1.end(); it++) {
		cout << it->first << " " << it->second<<"\n";
	}cout << "\n\n\n"; 
	//또는 
	for (auto x : m1) cout << x.first << " " << x.second << "\n"; 
}

 

 

 

맵과 벡터의 활용

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std; 
int n; 
map<int, int> order;
bool cmp(pair<int, int> a, pair <int, int> b) {
	if (a.second == b.second) {
		return order[a.first] < order[b.first]; 
	}
	else return a.second > b.second; 
}
int main() {
	cin >> n;
	int b; cin >> b;
	map<int, int> m;
	int s = 1;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		m[a]++;
		if (!order[a])order[a] = s++;
	}
	vector <pair<int, int>> v(m.begin(), m.end());
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v[i].second; j++) {
			cout << v[i].first << " "; 
		}
	}
	return 0;
}

 

2910번: 빈도 정렬