map & set

알고리즘(코딩테스트)

map & set

gbleem 2025. 2. 5. 15:45

1. map

1-1. map 기본 개념

key와 value 쌍으로 이루어져 있으며, key를 통해 value값에 O(1)에 접근할 수 있는 자료구조
검색, 삽입, 삭제가 평균적으로 O(logN)의 복잡도를 가진다.
내부 구현은 레드-블랙 트리로 되어있다.

1-2. 레드 블랙 트리

레드 블랙 트리는 이진 탐색 트리의 일종인데, 치우치는 값이 들어온 경우(편향된 경우) 를 방지하기 위해 트리의 높이를 logN으로 유지해주는 개선된 이진 탐색 트리이다.
편향된 트리의 경우 탐색 시간이 길어져, O(logN) 복잡도가 불가능해진다.
- 왜냐하면, 이진 탐색 트리가 기본적으로 선택한 노드를 기반으로 왼쪽은 작은 값 오른쪽은 큰 값으로 이루어져 있어서 값을 반씩 쪼개면서 찾기 때문에 빠른 탐색 O(logN) 을 할 수 있는데
- 편향된 경우 빠른 탐색이 불가능해진다. 최악의 경우 O(N) 복잡도가 되어버린다.

레드 블랙 트리의 특징
1. 루트는 검정 노드
2. 연속해서 빨강 노드가 존재할 수 없다.
3. 전체 트리를 보면, 루트를 기준으로 리프까지 갈 때까지 검정 노드의 갯수가 모든 경우에 있어서 같다.
  - 17 -> 9 -> 3 에서 검정 노드 2개
  - 17 -> 19 -> 18 에서 검정 노드 2개
  - 나머지 모든 경우에서도 검정 노드는 2개로 이루어져있다.

레드 블랙 트리 동작
- 데이터 추가
  - 새로운 노드는 빨강 노드이다.
  - 들어왔을때 규칙에 어긋나는 경우 아래의 동을 수행한다.
- 데이터 삭제
  - 균형을 맞추는 동작이 필요

1 - 3. map C++ 코드

함수들
- insert
- erase
- find
- [ ] operator
- size
- at
주의점
- [ ] 를 통해 값을 추가할 때 이전에 같은 key값이 있었다면, 덮어 써버리지만 insert로 추가할 때는 현재 insert 하는 값이 무시된다.
- at을 사용할 때 없는 key값을 입력하면 런타임 에러가 발생한다.
예제 코드

#include <iostream>
#include <map>
using namespace std;

int main()
{
	map<string, int> m;

	m["apple"] = 1000;
	m["banana"] = 500;
	m.insert({ "cookie", 800 });
	
	cout << m["apple"] << "\n"; //1000
	m["apple"] = 10;
	cout << m["apple"] << "\n"; //10
	m.insert({ "apple", 1 });
	cout << m["apple"] << "\n"; //10

	cout << m.at("banana") << "\n"; //500
	//cout << m.at("kiwi") << "\n"; //error

	if (m.find("cookie") != m.end())
		cout << "yes!\n";
	else
		cout << "no!\n";
	//yes! 출력

	cout << "size : " << m.size() << "\n"; //3
	m.erase("kiwi"); //무시
	m.erase("cookie");
	cout << "size : " << m.size() << "\n"; //2
}

2. set

2 - 1. set 기본 개념

키만 저장하는 map이라고 생각하면 쉽다.
중복이 불가능하다!
검색, 삽입, 삭제가 평균 O(logN)

2 - 2. set C++ 코드

함수들
- insert
- erase
- find
- size
- lower_bound: 넣은 값보다 크거나 같은 값 반환
- upper_bound: 넣은 값보다 큰 값 반환
주의점
- lower_bound 랑 upper_bound가 찾지 못한 경우는 end() 반환한다.
예제 코드

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s;

	s.insert(10);
	s.insert(20);
	s.insert(30);
	s.insert(40);
	s.insert(50);

	cout << "size: " << s.size() << "\n"; //5
	s.insert(10); //무시
	cout << "size: " << s.size() << "\n"; //5

	if (s.find(20) != s.end())
		cout << "yes!\n";
	else
		cout << "no!\n";
	//yes 출력

	s.erase(30);
	s.erase(100); //무시

	if (s.find(30) != s.end())
		cout << "yes!\n";
	else
		cout << "no!\n";
	//no 출력

	auto it1 = s.lower_bound(60);
	if (it1 != s.end())
		cout << "yes!\n";
	else
		cout << "no!\n";
	//no 출력

	auto it2 = s.upper_bound(50);
	if (it2 != s.end())
		cout << "yes!\n";
	else
		cout << "no!\n";
	//no 출력

	auto it3 = s.lower_bound(50);
	if (it3 != s.end())
		cout << *it3 << "\n";
	else
		cout << "no!\n";
	//50 출력

	auto it4 = s.lower_bound(44);
	if (it4 != s.end())
		cout << *it4 << "\n";
	//50 출력
}

3. multimap and multiset

map과 set인데 중복을 허용하는 자료구조이다. (잘 사용하지는 않았던 것 같다.)
기억할 만한 것
- multimap의 equal_range 함수
  - key값을 넣었을 때 해당하는 key를 가지는 모든 요소의 범위를 return 해준다.
  - multimap의 경우 key값으로 시작하는 iterator와 끝 iterator를 pair로 return 해주는 것이다.
  - 그냥 map의 경우 equal_range와 lower_bound는 같은 값을 리턴할 것이다.

//함수 시그니처
std::pair<iterator, iterator> equal_range(const Key& key);

#include <iostream>
#include <map>
using namespace std;

int main()
{
	multimap<int, string> mm;

	mm.insert({ 1, "apple" });
	mm.insert({ 1, "kiwi" });
	mm.insert({ 1, "banana" });

	auto range = mm.equal_range(1);
	//auto 실제 타입: pair<multimap<int, string>::iterator, multimap<int, string>::iterator> 

	for (auto it = range.first; it != range.second; ++it)
	{
		cout << it->second << " "; //appple kiwi banana
	}
}

4. 문제 풀어보기

문제:

n개의 단어(string) 를 입력받아, 등장횟수를 기준으로 오름차순 정렬하며 같은 등장횟수인 경우 단어의 사전순으로 정렬하기

내 풀이
- map을 통해서 빈도수를 체크 + 사전순 정렬
- multimap을 통해 빈도수로 재정렬

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

int main()
{
	int n;
	map<string, int> m1;
	multimap<int, string> m2;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		string name;
		cin >> name;

		m1[name]++; //{string, value}
	}

	for (auto mi1 : m1)
	{
		m2.insert({ mi1.second, mi1.first });
	}
	
	int grade = 0; //등수
        int cnt = 1;
        int before = -1; //저장할 값
        
        for (auto mi2: m2)
        {			
        	//만약 이전 값이랑 같은 경우
        	if (before == mi2.first)
        	{			
        		cnt++;
        		cout << mi2.second << ": " << grade << "\n";
        	}
        	else
        	{		
        		grade += cnt;
        		cout << mi2.second << ": " << grade << "\n";
        		cnt = 1;
        	}			
        	before = mi2.first;
        }
}

정답 풀이
- map의 값을 vector로 복사하기! (기억할 것)
- 람다식 (자주 써보기)

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

int main()
{
	int n;
	map<string, int> m1;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		string name;
		cin >> name;

		m1[name]++; //{string, value}
	}

	vector<pair<string, int>> vec(m1.begin(), m1.end());
	sort(vec.begin(), vec.end(), [](const auto& a, const auto& b)
		{
			if (a.second == b.second)
				return a.first < b.first;
			return a.second < b.second; 
		}
	);
	int rank = 0;
    int prevFrequency = -1;
    
    for(int i = 0; i < vec.size(); ++i)
    {
    	if(vec[i].second != prevFrequency)
        {
        	rank = i + 1;
            prevFrequency = vec[i].second;
        }
        cout << vec[i].first <<": " << rank << "\n";
    }
	
}