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