BOJ 10816 숫자 카드 2

이 문제는 상근이가 가지고 있는 숫자 카드 N개 중 주어진 M(정수)를 몇개씩 가지고 있는지 구한는 문제이다. N은 -10,000,000 ~ 100,000,000 사이의 숫자로 중복된 값이 들어올 수 있다. 이를 해결하기 위해 N개의 카드 중 특정 숫자가 몇개 존재하는지 체크를 해야한다.

 

가장 간단한 방법은 카드에 적혀 있는 숫자를 배열의 인덱스로 하여 카운팅 해주는게 편리한데 그렇게 할 경우 인덱스 범위가 0~ 200,000,000이 되어 해당 크기의 배열을 정의할 수 없다. 따라서 다른 방법을 생각해야한다.

 

생각해낸 방법은 백터를 이용하여 N을 정렬한 후 순차 탐색하면서 이전의 값이랑 중복되는지 안되는지 확인하여 새로운 해싱 백터를 만드는 것이다. 자세한 방법은 아래 코드에서 확인할 수 있다.

 

위의 방법으로 중복된 값을 카운팅 하여 새로운 백터로 만들었다고 가정하자. 이제 생각하야 할 부분은 M의 값이 백터에 어느 위치에 있는지 찾아야 한다. 

 

정렬된 배열에서 특정 숫자를 빠르게 찾는 방법은 이분탐색을 활용하면 O(logN)의 시간 복잡도로 찾을 수 있고 찾아야 하는 숫자가 M개 이므로 O(MlogN)만에 답을 찾을 수 있다. 

#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());

	
	// 이 부분이 기존의 백터를 해싱하여 pair<int,int> 타입으로 새로운 백터를 생성한다.
	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]);
	}

}