[백준] 10816번: 숫자 카드 2 (C++ 풀이)

문제

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

 

풀이

처음에는 그냥 multiset으로 count해서 풀었다. 시간초과가 났다.

입력, 출력하는데서 시간초과가 났나,,,하고 다시 조금 고치고 냈지만 맞을리가 없었다.

질문검색을 폭풍 서치한 결과

unordered_map을 사용해야한다는 힌트를 얻었다.

 

key에 카드를 저장하고 value에 개수를 저장했다.

unordered_map은 key를 정렬하지 않고 저장하는 map으로서

map에서 탐색하면 O(logN)이 걸리는 반면

unordered_map에서 탐색하면 O(1)이 걸린다.

 

코드

https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/10816.cpp

 

결과