[BOJ/C++] 10816 숫자 카드 2

문제

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

풀이

입력 개수와 찾는 개수가 전부 50만개이므로 vector에서 find로 직접 찾으면 시간초과난다. 이분탐색 이용해야한다.

🌳이분탐색 stl : lower_bound, upper_bound
lower_bound : 찾는 값 이상의 수가 처음 나타나는 위치
upper_bound : 찾는 값 초과의 수가 처음 나타나는 위치

✨배열을 정렬한 뒤에 upper_bound - lower_bound하면 개수가 나온다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int N, M;
	vector<int> v;

	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	sort(v.begin(), v.end());
	cin >> M;
	for (int i = 0; i < M; i++) {
		int tmp;
		cin >> tmp;
		cout << upper_bound(v.begin(), v.end(), tmp) - lower_bound(v.begin(), v.end(), tmp) << " ";
	}

	return 0;
}