[백준] 10816 숫자 카드 2 / 정렬, 해시테이블, upper -lower bound (C++)

처음에는 정렬하고 find를 사용해서 풀어보려고 했다.
하지만 역시나 시간초과

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

int main()
{
	int N, M;
	cin >> N;
	vector<int> v(N);
	
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
	}

	sort(v.begin(), v.end());


	cin >> M;

	for (int i = 0; i < M; i++)
	{
		int tmp, cnt = 0;
		cin >> tmp;
		vector<int>::iterator it = find(v.begin(), v.end(), tmp);

		if (it == v.end())
		{
			cout << 0 << " ";
			continue;
		}
		else
		{
			for (int j = it - v.begin(); j < v.size() && v[j] == tmp; j++)
			{
				cnt++;
			}
			cout << cnt << " ";
		}
	}

	return 0;
}

가능한 풀이는 unordered_map 을 사용하는 방식이 있다.
처음에는 map을 이용하려 했으나 그러면 모든 숫자에 공간을 잡아놓아야 하지 않냐는 생각에 안했었는데, 이는 크게 오해한 것
어차피 key, value 쌍이기 때문에 하나씩 넣으면 된다... 내가 생각한 것은 pair<int, int>의 특성이다.

unordered_map은 key-value 쌍을 저장하는 자료 구조로, key가 존재하지 않는 경우에는 기본적으로 0을 반환합니다. 이 동작은 C++의 unordered_map 자료 구조의 특징

기본적으로 unordered_map은 key가 존재하지 않는 경우에 해당 key에 대한 값을 0으로 초기화하고, 이미 존재하는 key의 경우 해당 값에 접근할 수 있도록 해준다. 이렇게 하면 키가 맵에 없어도 프로그램이 중단되지 않고 예외가 발생하지 않는다.

그리고 또 하나, map과의 차이는 map은 이진 트리로 구성되어있고,
unordered_map은 hash table로 구성되어있다.
map은 이진 트리니까 key값을 기준으로 sorting 되어있고, unordered는 hash table이니까 sorting 되지 않는다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

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

	int N, M;
	cin >> N;
	unordered_map<int, int> uMap;
	
	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;
		uMap[tmp]++;
	}


	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int tmp;
		cin >> tmp;
		cout << uMap[tmp] << " ";
	}

	return 0;
}

추가 풀이
upper_bound -> 특정 값보다 큰 값이 처음으로 나타나는 곳의 위치
lower_bond -> 특정 값 이상의 값이 처음으로 나타나는 곳의 위치

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

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

	int N, M;
	cin >> N;
	vector<int> v(N);
	
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
	}

	sort(v.begin(), v.end());

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int tmp;
		cin >> tmp;
		cout << upper_bound(v.begin(), v.end(), tmp) - lower_bound(v.begin(), v.end(), tmp) << " ";
	}

	return 0;
}