해쉬맵

[baekjoon 10816] 숫자 카드2 - Hashmap, 이분탐색 (C++)

www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 입력 수들을 받고, 찾고자 하는 수에 해당하는 수가 몇 개가 있는지 출력하는 문제다. 입력 개수는 50만 개, 찾는 수 또한 50만 개로 일반적인 배열에 넣고 선형 탐색을 하게 되면 O(N^2)로 시간제한 1초를 넘기게 된다. 보통 c++기준 N = 1억이면 1초라고 한다. 따라서 보통의 시간 복잡도가 O(1)인 HashMap을 이용하거나 O(logN)인 이분 탐색을 이용해야 ..