Algorithm/이분탐색

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

Mini_96 2024. 1. 2. 10:17

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

 

10816번: 숫자 카드 2

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0

www.acmicpc.net

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;
}