BOJ 10816 숫자 카드 2

이 문제는 N개의 카드중에서 M개의 카드 숫자가 몇개 있는지 찾는 문제이다. 단순한게 브루트포스 방법 O(n^2)으로 문제를 해결하려고 시도한다면 N = 500000, M = 500000 이므로 시간초과가 발생한다. 따라서 특정 숫자가 어디에 있는지 빠르게 탐색하기 위해 이진탐색으로 접근해야 한다.

 

이진탐색을 하기 위해서는 우선 상근이의 숫자 카드 N이 오름 차순으로 정렬이 되어있어야 한다. 이때 핵심은 중복된 숫자 카드를 어떻게 표현할 것인가 이다.

 

오름 차순 정렬 후 앞쪽부터 순회하면서 중복된 숫자를 pair<int,int> 로 변환 시켜준다. 

예를들어 N이 -10, -10, 1, 3, 5, 10, 10, 10 일경우 {-10,2}, {1,1}, {3,1}, {5,1}, {10,3} 과 같은 형태로 변환을 시켜준다.

이후 이진탐색을 진행한다.

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

vector<int> nv, mv;
vector<pair<int, int>> h;
int result;

void BS(int l,int r,int v)
{
	if(l > r)
	{
		cout << 0 << " ";
		return;
	}

	int mid = (l + r) / 2;

	if(h[mid].first == v)
	{
		cout << h[mid].second<<" ";
	}
	else if(h[mid].first < v)
	{
		BS(mid + 1, r, v);
	}
	else
	{
		BS(l, mid - 1, v);
	}
}

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

	int n, m;

	cin >> n;

	for(int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		nv.push_back(num);
	}

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

	
	//백터 변환
	for(int e:nv)
	{
		if(h.empty() || h.back().first != e)
		{
			h.push_back({ e, 1 });
		}
		else
			h.back().second += 1;
	}

	cin >> m;

	for(int i = 0; i < m; i++)
	{
		int num;
		cin >> num;
		mv.push_back(num);
	}

	for(int i = 0; i < m; i++)
	{
		BS(0, h.size()-1, mv[i]);
	}

}