백준 [10546] 배부른 마라토너

출처 : https://www.acmicpc.net/problem/10546

10546번: 배부른 마라토너

 

 

해시를 이용하여 풀어야하는 문제

unordered_map을 이용

map_name[key] = value 

탐색 방법

• index로 접근할 수 없고, iterator로 접근
• key : iter -> first, iter -> second

map과 unordered_map의 차이

• unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도 O(1)
• map 은 binary search tree로 탐색 시간 복잡도 O(log n)
• unordered_map은 map과 달리 key또는 value 기준으로 sorting 되어 있지 않음. key 값으로 hash value를 찾는데 map보다 시간이 적게 걸림.
• 데이터가 많은 경우에는 unordered_map이 map보다 성능면에서 유리하지만, 문자열을 키로 사용하는 경우 문자열이 길어질수록 map에 비해 성능이 떨어질 수 있음.

검색해본 결과)

결론적으로 key를 이용하여 정렬을 해야하는 경우를 제외하고 대량의 데이터를 저장할 때는 unordered_map을 사용하는 것이 좋다고 함.