[백준 10816] 숫자 카드 2, C++

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

10816번: 숫자 카드 2

 본 문제는 n개의 숫자 카드를 보유하고 있을 때, 해당 숫자가 적혀있는 숫자 카드의 개수를 m번 출력하는 문제다. 이분 탐색을 이용하는 문제로 개수를 구하는 문제는 lower_bound와 upper_bound로 구할 수 있다.

• lower_bound : 크거나 같은 수 중 첫 번째
• upper_bound : 큰 수 중 첫 번째

이러한 특징을 가지고 있기 때문에 upper_bound에서 lower_bound를 빼면 동일한 숫자의 개수가 나온다.

C++에는 lower_bound와 upper_bound를 반환해주는 equal_range 함수가 있다. 동일한 결과가 나오지만 equal_range가 조금 더 빠르다.

#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main() {
    int n, m;
    scanf("%d", &n);
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    vector<int> ans;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int num;
        scanf("%d", &num);
        auto upper = upper_bound(v.begin(), v.end(), num);
        auto lower = lower_bound(v.begin(), v.end(), num);
        ans.push_back(upper-lower);
        // auto range = equal_range(v.begin(), v.end(), num);
        // ans.push_back(range.second - range.first);
    }
    for (int i = 0; i < ans.size(); i++) {
        printf("%d ", ans[i]);
    }
    printf("\n");
}