백준 10816 - 숫자 카드 2

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

10816번: 숫자 카드 2

풀이

탐색하려는 배열에 중복이 있다면 target이 되는 수를 찾아내도, 이 수가 몇개 있는지는 알아낼 수 없다. 따라서 algorithm 헤더의 upper/lower_bound를 사용하면 target이 되는 수들의 마지막 주소와 시작 주소를 얻을 수 있다. 따라서 upper_bound - lower_bound를 계산하면 총 개수도 계산할 수 있다.

 

코드

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

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int N,M,a,b;
    cin>>N;
    vector<int> v1;
    vector<int> v2;

    for(int i=0; i<N; i++)
    {
        cin>>a;
        v1.push_back(a);
    }

    cin>>M;
    for(int i=0; i<M; i++)
    {
        cin>>b;
        v2.push_back(b);
    }

    sort(v1.begin(),v1.end());

    for(auto err:v2)
    {
        int cnt;
        cnt = upper_bound(v1.begin(),v1.end(),err)-lower_bound(v1.begin(),v1.end(),err);
        cout<<cnt<<" ";
    }
    return 0;
}