[c/c++] 백준 10816(Silver 4)

🔨 문제

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

<요약>
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

🔨 해결방법

1. 벡터를 이용해 값을 입력 받고 sort (이진 탐색 해야하기 때문)

2. algorithm 라이브러리의 lower_bound와 upper_bound를 이용

lower_bound, upper_bound ❓

c++에서는 binary_search함수와 함께 lower_bound, upper_bound함수를 제공한다.

• 오름차순으로 정렬된 자료에서 특정한 숫자가 몇 번 나오는지 탐색하고자 할 때 유용하게 사용 가능

• upper_bound : 찾으려는 key값보다 초과하는 숫자가 몇 번째에서 처음 등장하는지 찾기 위함

• lower_bound : 찾으려는 key값보다 같거나 큰 숫자가 몇 번째에서 처음 등장하는지 찾기 위함

  사용 방법 - lower_bound(시작 지점, 끝 지점, 찾는 값)

ex. 벡터 v에서 4가 몇 개 있는지 찾아봐라

vector <int> v = {1,2,3,4,4,4,6,6,7};
cout << "number of 4 : " << upper_bound(v.begin(), v.end(), 4) 
           - lower_bound(v.begin(), v.end(), 4); 

출력결과는 3 이 나온다.
4보다 큰 숫자가 나오는 위치(index = 6) - 4이상의 숫자가 처음으로 나오는 위치(index = 3)

🔨 코드

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

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

	int n;
	cin >> n;
	vector <int> v;

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

	int m;
	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;
}