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

 

찾고자하는 숫자가 얼마나 많이 있는지 구하는 문제였다.

C++ STL에 있는 lower_bound와 upper_bound를 사용해도 좋지만 직접 구현하여도 좋다.

하지만 실제 시험에서는 제한 시간이 모자라거나, 긴장해서 실수할 수도 있기 때문에 STL을 쓰는 것이 더 좋을 것 같다.

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

int n, m;
int a[500001];

int lower_idx(int target, int n)
{
	int st = 0;
	int ed = n;

	while (st < ed)
	{
		int mid = (st + ed) / 2;
		if (a[mid] < target)
		{
			st = mid + 1;
			mid = (st + ed) / 2;
		}
		else if (a[mid] >= target)
		{
			ed = mid;
		}
	}
	return st;
}

int upper_idx(int target, int n)
{
	int st = 0;
	int ed = n;

	while (st < ed)
	{
		int mid = (st + ed) / 2;
		if (a[mid] <= target)
		{
			st = mid + 1;
		}
		else if (a[mid] > target)
		{
			ed = mid;
		}
	}
	return st;
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	sort(a, a + n);

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int t;
		cin >> t;
		cout << upper_idx(t, n) - lower_idx(t, n) << '\n';
	}
}