10816번 - 이분 탐색 - 숫자 카드 2

[ 풀이 ]

lower_bound와 upper_bound를 이용했다.
(탐색된 값이 초과되는 지점 - 탐색값이 시작되는 지점)으로 중복된 개수를 구하였다.

[ 코드 ]

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n = 500000;
int m = 500000;
vector<int> cards;

int checkCardsNum(int num) { //중복되는 카드 개수 세기
	auto minAdd = lower_bound(cards.begin(), cards.end(), num);
	auto maxAdd = upper_bound(cards.begin(), cards.end(), num);
	int result = maxAdd - minAdd;
	return result;
}

int main() {
	scanf("%d", &n);

	int card = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &card);
		cards.push_back(card);
	}
	
	sort(cards.begin(), cards.end());

	int minNum = cards.front();
	int maxNum = cards.back();
	
	scanf("%d", &m);
	int target = 0;
	for (int i = 0; i < m; i++) {
		scanf("%d", &target);
		if (target > minNum && target < maxNum) {
			int left = 0;
			int right = m - 1;
			bool isExist = false;
			while (left <= right) {
				int mid = (left + right) / 2;
				if (cards[mid] == target) { //범위 내에서 값이 존재하는 경우
					printf("%d\n", checkCardsNum(target));
					isExist = true;
					break;
				}
				else if (cards[mid] < target) {
					left = mid + 1;
				}
				else {
					right = mid - 1;
				}
			}

			if (!isExist) {
				printf("0\n");
			}
		}

		else if (target == minNum || target == maxNum) {
			printf("%d\n", checkCardsNum(target));
		}

		else {
			printf("0\n");
		}
	}

	return 0;
}