백준 단계별로 풀어보기에서 집합과 맵 부분의 14425번을 풀다가 처음으로 손도 못대고 막혔다. 맵을 쓰지 않으니 시간 초과가 나고.. 맵을 쓰자니 C++에서 어떻게 구현을 하는지도 모르겠고 STL도 어떻게 쓰는지도 모르겠고.. 옛날에 자바할 때 한 번 써본 기억이 있는데 너무 오래 전이라 지금은 개념정도밖에 기억나지 않는다. 그래서 이왕 이렇게 된 김에 정리도 하고 STL도 암기하자는 생각으로 글을 쓴다.
문제 링크: https://www.acmicpc.net/problem/14425
14425번: 문자열 집합
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어
www.acmicpc.net
< 맵(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()