[백준 #10816] 숫자 카드 2 (C++)

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

10816번: 숫자 카드 2

 

이 문제는 upper_bound와 lower_bound를 사용하여 풀었다.

upper_bound와 lower_bound는 이진 탐색을 기반으로 하는 탐색 방법으로,

upper_bound는 찾으려는 원소보다 큰 숫자가 처음 나오는 위치를

lower_bound는 찾으려는 원소가 처음 나오는 위치

(없다면 그거보다 큰 원소가 처음 나오는 위치)를 알려주는 것이다.

 

처음에 상근이가 가지고 있는 숫자 카드의 개수(n)를 입력하면

크기가 n인 벡터 v를 생성해주고 for문을 사용하여 숫자 카드를 입력한다.

 

그다음 상근이가 가지고 있는 카드인지 구할 숫자의 개수(m)를 입력하면

for문을 통해 그 숫자만큼 입력하게 해주었는데,

이때 upper_bound와 lower_bound를 사용하여

입력한 값보다 큰 수가 처음 나오는 위치 - 입력한 값(or 보다 큰)이 처음 나오는 위치

를 계산하여 입력한 값의 숫자가 벡터 v에 몇 번 나오는지 계산하였다.

 

이진 탐색과 마찬가지로 upper_bound와 lower_bound는 사용 전에

해당 배열이나 벡터를 오름차순으로 정렬해야 된다.

 

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

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

	int n, m;
	cin >> n;
	vector<int> v(n);	// 상근이가 가지고 있는 카드

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	cin >> m;
	for (int i = 0; i < m; i++) {
		int num;
		cin >> num;
		
		cout << upper_bound(v.begin(), v.end(), num) - lower_bound(v.begin(), v.end(), num) << " ";
	}
	
	return 0;
}