[백준] 10816 숫자 카드 2

[백준] 10816 숫자 카드 2

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

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

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

	int n, m;
	vector<int> vec;

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		vec.push_back(input);
	}
	vec.push_back(10000001);
	vec.push_back(-10000001);
	sort(vec.begin(), vec.end());

	cin >> m;
	while (m--) {
		int input;
		cin >> input;

		int left, right;

		//가장 왼쪽의 원소에 접근하도록 이분탐색
		int high = vec.size()-1;
		int low = 0;
		while (low < high) {
			int mid = (high + low) / 2;
			if (vec[mid] < input) low = mid + 1;
			else high = mid;
		}
		left = high;

		//가장 오른쪽의 원소에 접근하도록 이분탐색
		high = vec.size() - 1;
		low = 0;
		while (low < high) {
			int mid = (high + low + 1) / 2;
			if (vec[mid] <= input) low = mid;
			else high = mid - 1;
		}
		right = high;
		
		cout << right - left + 1 << " ";
	}

	return 0;
}

• upper bound: 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치
• lower bound: 찾고자 하는 값 이상이 처음으로 나타나는 위치

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

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

	int n, m;
	vector<int> vec;

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		vec.push_back(input);
	}
	vec.push_back(10000001);
	vec.push_back(-10000001);
	sort(vec.begin(), vec.end());

	cin >> m;
	while (m--) {
		int input;
		cin >> input;

		int left, right;

		left = upper_bound(vec.begin(), vec.end(), input - 1) - vec.begin();
		right = upper_bound(vec.begin(), vec.end(), input) - vec.begin() - 1;

		cout << right - left + 1 << " ";
	}

	return 0;
}