[백준] 10816번 : 숫자 카드 2

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 이진 탐색 중에서 lowerBound와 upperBound를 이용했다. 각 숫자 카드에 대해 해당 숫자가 가장 먼저 나오는 인덱스와 해당 숫자를 가장 먼저 초과하는 인덱스를 구해 해당 숫자 카드의 개수를 확인했디.

1) 배열에 가지고 있는 숫자 카드들을 차례대로 삽입한다.

2) 이진 탐색을 하기 위해서는 배열이 정렬되어있어야 하기 때문에 sort로 오름차순 정렬해준다.

3) 개수를 찾고자 하는 수에 대해 lowerBound와 upperBound 함수에 target으로 입력해
해당 수가 가장 먼저 나오는 인덱스 a와 해당 수를 가장 먼저 초과하는 인덱스 b를 구해 b - a를 계산하면 해당 수의 개수를 알 수 있다.

🖥️ 풀이 코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int arr[500000];

int lowerBound(int arr[], int start, int end, int target)
{
	int mid;

	while (end > start)
	{
		mid = (start + end) / 2;

		if (arr[mid] >= target)
			end = mid;
		else if (arr[mid] < target)
			start = mid + 1;
	}
	return end;
}

int upperBound(int arr[], int start, int end, int target)
{
	int mid;

	while (end > start)
	{
		mid = (start + end) / 2;

		if (arr[mid] > target)
			end = mid;
		else if(arr[mid] <= target)
			start = mid + 1;
	}
	return end;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();
	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		arr[i] = num;
	}

	sort(arr, arr + n);

	int m;
	cin >> m;

	string str;
	for (int i = 0; i < m; i++)
	{
		int num;
		cin >> num;
		str += to_string(upperBound(arr, 0, n, num) - lowerBound(arr, 0, n, num)) + ' ';
	}

	cout << str;
	return 0;
}