https://www.acmicpc.net/problem/10816
lower_bound
와 upper_bound
함수를 이용하여 찾고자 하는 수가 등장하는 처음과 마지막+1 위치를 구하고 그들의 차를 출력하였다.
오름차순 정렬된 배열에서 찾고자 하는 수 value가 있을 때
lower_bound(first, last, value)
: [first, last) 안의 원소들 중, value보다 크거나 같은 첫 번째 원소를 리턴한다. 그런 원소가 없다면 last를 리턴한다.
upper_bound(first, last, value)
: [first, last) 안의 원소들 중, value보다 큰 첫 번째 원소를 리턴한다. 그런 원소가 없다면 last를 리턴한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, target;
cin >> n;
vector<int> card(n);
for(int i=0; i<n; i++) cin >> card[i];
sort(card.begin(), card.end());
cin >> m;
while(m--) {
cin >> target;
cout << upper_bound(card.begin(), card.end(), target)
- lower_bound(card.begin(), card.end(), target) << " ";
}
return 0;
}