백준 10816번 숫자 카드 2 C++

unordered_map 사용 코드

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	cin >> n;

	unordered_map<int, int> um;
	int card = 0;
	for (int i = 0; i < n; ++i) {
		cin >> card;
		++um[card];
	}

	int m = 0;
	cin >> m;
	for (int i = 0; i < m; ++i) {
		cin >> card;
		cout << um[card] << " ";
	}

	return 0;
}

 

이진 탐색이 더 빠름

-> O(1)인 해쉬맵보다 O(logN)인 이진 탐색이 빠른 이유

https://www.acmicpc.net/board/view/57406

 

이진 탐색을 활용한 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[500002];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	cin >> n;
	int card = 0;
	for (int i = 0; i < n; ++i) {
		cin >> card;
		arr[i] = card;
	}
	sort(arr, arr + n);

	int m = 0;
	cin >> m;
	for (int i = 0; i < m; ++i) {
		cin >> card;
		cout << upper_bound(arr, arr + n, card) - lower_bound(arr, arr + n, card) << " ";
	}

	return 0;
}

 

이진 탐색 기반의 탐색 방법 upper_bound, lower_bound

 

upper_bound : 찾고싶은 key 값보다 큰 값이 최초로 나타나는 위치 return

lower_bound : 찾고싶은 key 값, 또는 그 보다 큰 값이 최초로 나타나는 위치 return

따라서 upper_bound - lower_bound : 찾고싶은 값의 개수

 

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

10816번: 숫자 카드 2