백준 10816 숫자카드2 c++ // 이분탐색, upper_bound, lower_bound

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

10816번: 숫자 카드 2

1. upper_bound, lower_bound(begin, end, target)

이분탐색으로 target원소중 가장 우측, 좌측 인덱스 반환

 

2.전체코드

#include <bits/stdc++.h>
using namespace std;

int n,m;
vector<int> v;

int main() {
    /*
    * 이진탐색 -> 2^50 -> 시간초과
    * 역발상 : target에서 start로 수렴하도록 변경!
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while (n--) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());
    cin >> m;
    while (m--) {
        int target;
        cin >> target;
        cout << upper_bound(v.begin(), v.end(), target) - lower_bound(v.begin(), v.end(), target) << " ";
    }
    return 0;
}