Map

백준 단계별로 풀어보기에서 집합과 맵 부분의 14425번을 풀다가 처음으로 손도 못대고 막혔다. 맵을 쓰지 않으니 시간 초과가 나고.. 맵을 쓰자니 C++에서 어떻게 구현을 하는지도 모르겠고 STL도 어떻게 쓰는지도 모르겠고.. 옛날에 자바할 때 한 번 써본 기억이 있는데 너무 오래 전이라 지금은 개념정도밖에 기억나지 않는다. 그래서 이왕 이렇게 된 김에 정리도 하고 STL도 암기하자는 생각으로 글을 쓴다.

 

문제 링크: https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

< 맵(Map) >

키(Key)와 값(Value)로 이루어진 자료구조.

키는 중복을 허용하지 않음.

 

맵을 이용한 자료구조

해시맵(Hash Map) - 해시함수로 매핑

트리맵(Tree Map) - 키값을 이용해 순서대로 정렬하여 저장 가능

연결해시맵(Linked Hash Map) - 데이터를 입력한 순서대로 저장

 

음 근데 다른 것들은 이런 것들이 있구나 정도로 넘어가고 맵의 개념과 사용법만 알면 될 것 같다.

 

< STL >

헤더: #include <map>

선언: map<key type, value type>이름

e.g)

map<int, string> map1;

 

값 찾기: map1.find() 만약 찾지 못하면 map1.end() 반환

 

첫번째와 마지막: map1.begin(), map1.end()

 

요소 삭제: map1.erase()