[C++] 백준 10816번 숫자 카드 2

처음에는 무지성으로 풀다가 음수인 숫자를 못보고 잘못 풀었음을 느꼈다

음수를 받을 때 어떻게 하면 좋을지 좀 많이 고민했었는데

이분 탐색으로도 안풀려서

한시간 고민하다가 안되서 결국 구글링

 

C++의 algorithm에는 다양한 기능들이 있다

그 중 lower_bound, upper_bound라는 기능들이 있는데 이거를 활용하면

정말 간단하게 풀리는 문제였다

 

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

int main() {

	int n, m, x, y;
	cin >> n;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	
	
	cin >> m;
	vector<int> answer(m);
	for (int i = 0; i < m; i++) {
		cin >> y;
		auto upper = upper_bound(v.begin(), v.end(), y);
		auto lower = lower_bound(v.begin(), v.end(), y);

		answer[i] = upper - lower;
	}
	for (int n : answer) {
		cout << n << " ";
	}
	cout << "\n";
	
    return 0;
}