[CPP] 1620 - unordered_map

1620 - 나는야 포켓몬 마스터 이다솜

https://www.acmicpc.net/problem/1620

새롭게 알게된 자료형 - unordered_map

특징

- 해시 기반으로 검색하는 자로형 (검색이 빠름 O(1)의 복잡도)
- 삽입된 순서를 기억하지 않음
- 메모리 사용량 많음
- 자체적으로 정렬할 수 없음. 정렬하고 싶을 때는 vector 등의 자료형으로 변환한 후에 정렬해야 함.

 std::vector<std::pair<std::string, int>> sortingArray(entryRecord.begin(), entryRecord.end());
    std::sort(sortingArray.begin(), sortingArray.end(), 
        [](std::pair<std::string,int>& a, std::pair<std::string,int>& b)
        {
            return a.first > b.first;    
        });

언제 unordered_map을 사용하는 것이 좋을까요?

빠른 키-값 검색이 필요할 때
삽입, 삭제, 검색이 자주 발생할 때
순서가 중요하지 않을 때
데이터를 정렬할 필요가 없는 경우

문제에 적용한 이유

해당 문제는 빠른 찾기 연산이 필요한 문제였다. 처음에는 find를 사용했고 시간 초과가 계속 발생했다.
하지만 unordered_map을 적용한 후에도 cin 문제, cout을 사용했던 문제 등으로 시간 초과가 발생했다.
이렇게 시간 초과될만한 요소를 모두 바꿔주니 문제가 해결됐다.

map과 set과는 뭐가 다른가요?

map과 set은 기본적으로 정렬을 합니다...!
두 자료형의 차이로는 map은 pair로 저장하고 set은 단일값으로 저장된다는 점이 있다.
두 자료형은 모두 중복을 허용하지 않는다는 점에서 유용한 자료형인 것 같다.