백준 10816 숫자 카드 2

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

입력

첫째 줄: 상근이가 가지고 있는 숫자 카드의 개수 N
둘째 줄: 각 숫자 카드에 적혀있는 정수(-10,000,000보다 크거나 같고 10,000,000보다 작거나 같음)
셋째 줄: 숫자 M (1 <= M <= 500,000)
넷째 줄: 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수 (-10,000,000보다 크거나 같고 10,000,000보다 작거나 같음)

출력

입력으로 주어진 M개의 수에 대하여, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지 공백으로 구분해 출력

해결 방법

문제 입력과 출력 예제

1. 위에 나와있는 조건대로 모두 입력을 받는다.
2. 이분탐색을 위해 각 숫자 카드에 적힌 정수들을 정렬한다.
   위의 예제에서 '6 3 2 10 10 10 -10 -10 7 3'으로 카드 숫자들을 입력하면 이를 '-10 -10 2 3 3 6 7 10 10 10'으로 정렬한다.
3. 정렬된 배열에서 upper_bound와 lower_bound 함수를 이용하여 문제를 해결한다.

upper_bound(arr, arr+n, value)
upper_bound 함수는 배열에서 처음으로 특정 value 값을 초과하는 원소의 주소를 반환하고, 그러한 원소가 없으면 end값을 반환하는 함수

lower_bound(arr, arr+n, value)
lower_bound 함수는 배열에서 범위 내의 원소들 중 value 값보다 크거나 같은 첫 번째 원소의 주소를 반환하는 함수. 없으면 end값 반환

아래 예제를 살펴보면 다음과 같다.

4. 위의 예제에서 숫자 -10의 개수를 알고 싶다면 upper_bound(-10) - lower_bound(-10)을 하면 -10의 개수를 구할 수 있다.

전체 소스코드

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

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

        int n,m, num;

        cin>>n;

        vector<int> card(n);

        for(int i=0;i<card.size();i++) {
                cin>>card[i];
        }

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

        cin>>m;

        for(int i=0;i<m;i++) {
                cin>>num;

                auto start = lower_bound(card.begin(), card.end(), num);
                auto end = upper_bound(card.begin(), card.end(), num);

                cout<<end-start<<" ";
        }

        return 0;
}