[STL] map 활용 문제
요약
C++ STL Associative Container
key - value 형태
C++ STL map은 트리(Red-Black tree) 기반으로 추상화한 데이터 구조
다른 곳에 사용법은 많으니 사용법은 간단히 요약하고, 공부하며 직접 활용한 문제를 복기하고자 한다.
원형
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
> class map;
Key, Value type을 받는 템플릿 클래스
가장 중요한 건 Key는 유일하다는 점이다.
Compare 부분을 보면 사전 오름차순으로 정렬된다는 것을 알 수 있다.
어떻게 자동 정렬하는지 그 원리는
해쉬, 레드 블랙 트리를 이해해야 하는데,
지금 다루기엔 너무 복잡하니 넘어가자
사용법
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<int, string> dic;
dic[1] = "첫 번째"; // 삽입 1
dic.insert({ 2, "두 번째" }); // 삽입 2
for (auto iter = dic.begin(); iter != dic.end(); iter++) // iterator 순회
{
cout << iter->first << ", " << iter->second << '\n'; // first가 key, second가 value
}
cout << '\n';
dic.erase(1); // 삭제
cout << "key 1 erase" << '\n';
for (auto& elem : dic) // Range-based for문
{
cout << elem.first << ", " << elem.second << endl;
}
cout << '\n';
cout << "key 2 find" << '\n';
if (dic.find(2) != dic.end()) // find. 찾으면 찾은 위치 인덱스, 못 찾으면 dic.end() iterator 반환
{
cout << "key 2 찾았따." << '\n';
}
else
{
cout << "key 2 못!!! 찾았당." << '\n';
}
cout << '\n';
dic.clear(); // 모두 제거
cout << "dic 다 지웠당\n";
cout << "dic size: " << dic.size() << '\n'; // 사이즈
cout << "dic.empty() ? " << dic.empty() << '\n'; // 비어있는지 체크
return 0;
}
1, 첫 번째
2, 두 번째
key 1 erase
2, 두 번째
key 2 find
key 2 찾았따.
dic 다 지웠당
dic size: 0
다른 STL과 같이 공통 시퀀스들을 사용한다.
다만 인덱스가 없기 때문에 push_back(), front()와 같은 메서드는 없다.
물론 임의 접근(random access) 역시 불가능하다.
vector와 달리 모든 구간 삽입, 삭제, 찾기의 시간복잡도가 O(log(n)) 밖에 안 된다!!
기반 구조가 완전히 다르지만, 자매품
정렬하지 않는 unordered_map,
중복을 허용하는 multimap,
정렬하지 않으며 중복을 허용하는 unordered_multimap 이 있다.
사용처
게임 기획 시 우리 게임에선 보상 테이블의 보상 키값 - 보상량 식의 구조를 비롯한 테이블 구조 내에 많이 사용했다.
문제를 풀 때도 map을 많이 사용했다.
하지만 문제 풀이에서는 정렬 시간복잡도를 줄이기 위해 unordered_map 을 더 많이 사용했던 것 같다.
문제
두 집합에서 공통 키값인 교집합을 찾아야 하는 문제.
key의 유일성을 이용한 문제.
사전순임을 보고 정렬을 해야함을 알 수 있었다.
두 집합에서 공통 부분을 뺀 차집합을 구하는 문제
정렬을 이용하지 않고 map으로 풀었다.
맵 사이즈로 차집합의 사이즈를 구하기 위해 erase()를 사용해 제거해주었다.
중복된 종류는 하나로 친다. -> key가 유일한 map을 이용!
정렬이 필요 없으니 unordered !
n / 2 마리만 고려해 답을 내면 되는 쉬운 문제
phone_book의 길이가 1,000,000이기 때문에 무지성 O(n^2) 풀이는 불가능했다.
O(n logn) 혹은 O(n*m)(m은 전화번호 최대길이) 에는 끝장을 봐야 했다.
map으로 키-값 추가 시 자동 정렬되는데, 이러면 굳이 요소를 각각 비교할 필요가 없다.
중복되었다면 인접한 위치에 정렬되어 있을 것이고, 단 한 번이라도 중복되면 리턴하면 되기 때문이다.
iterator for문 하나로 지금 것과 다음 것만 비교해서,
접두어가 중복되면 false로 리턴해버리고, 중복 안 되면 iterator를 증가시켜 다음 요소와 다다음 요소를 비교하면 되었다.
문자열 비교는 substr()을 사용해 비교해주었다. 물론 flag 설정하고 for문 한 번 더 돌려 비교해도 된다.
이러면 시간복잡도 O(n*m)(m은 전화번호 최대길이)만에 수행이 가능하다.
항상 iterator for 문이 아닌 Range-based for 문을 사용했는데,
이 문제를 풀고 iterator for문의 효용성을 깨달았다.
참고
※ 틀리거나 개선할 부분이 있다면 알려주세요.
댓글남기기