백준 10816 숫자 카드 2

 

 

 

 

#include<iostream>
#include<vector>	
#include<algorithm>
using namespace std;
vector<int>my_card;
vector<int>find_card;

int n, m,answer=0;


int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> n ;
	for (int i = 0;i < n;i++) {
		int c;
		cin >> c;
		my_card.push_back(c);
	}
	cin >> m;
	for (int i = 0;i < m;i++) {
		int c;
		cin >> c;
		find_card.push_back(c);
	}
	sort(my_card.begin(), my_card.end());

	vector<int>answer(m);

	for (int i = 0; i < m; i++) {
		int target = find_card[i];
		auto lower = lower_bound(my_card.begin(), my_card.end(), target);
		auto upper = upper_bound(my_card.begin(), my_card.end(), target);
		answer[i] = upper - lower; // 범위 내의 요소 수를 계산
	}

	for (int i = 0;i < m;i++) {
		cout << answer[i]<<" ";
	}

	return 0;
}

탐색 과정에서 이진 탐색을 진행하였는데  알고리즘 헤더에 존재하는

upper_bound (arr.begin(),arr.end(),타겟); lower_bound(arr.begin(),arr.end(),타겟);을 이용함

사용하기 전에 벡터가 오름차순으로 정렬되어 있어야한다.

lower 는 타겟이 처음으로 나오는 인덱스를 반환하고 upper는 키값을 처음으로 초과하는 인덱스를 반환한다.

 

따라서 upper-lower을 계산하여 저장해주면 해당  타겟이 몇번 등장했는지 계산 가능하다