백준 10816 : 카드 게임 2 (upper_bound 알고리즘)

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

1. 접근

• 당연히 1초의 시간 제한이 있으므로 m개의 카드를 모두 다 확인할 수는 없다.
• algorithm 헤더에는 upper_bound 라는 유용한 함수가 있다.

upper_bound : 찾는 값 중 가장 작은 인덱스

• 이분탐색을 활용하여 만들어진 알고리즘이다.
• upper_bound 와 lower_bound 를 활용하여, 두 인덱스의 차를 구하면 출력값이 나온다.

2. 나의 풀이

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

int main() {
	vector<int> cards;
	int n, m;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int tem;
		cin >> tem;
		cards.push_back(tem);
	}

	sort(cards.begin(),cards.end());

	cin >> m;
	for (int i = 0; i < m; i++) {
		int tem;
		cin >> tem;

		auto upper = upper_bound(cards.begin(), cards.end(), tem);
		auto lower = lower_bound(cards.begin(), cards.end(), tem);

		cout << upper - lower<<" ";
	}
	cout << "\n";

	return 0;
}

3. 참고

https://blockdmask.tistory.com/168
직접 코드로 구현된 lower_bound, upper_bound