[BOJ] 10816번 숫자 카드 2 (C++)

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

10816번: 숫자 카드 2

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m, k;
	cin >> n;
	
	vector<int> v;
	for(int i = 0; i < n; i++){	
		cin >> k;
		v.push_back(k);
	}
	
	sort(v.begin(), v.end());
	
	cin >> m;
	
	for(int i = 0; i < m; i++){	
		cin >> k;
		auto l = lower_bound(v.begin(), v.end(), k);
		auto u = upper_bound(v.begin(), v.end(), k);
		cout << u - l << '\n';
	}
	
	return 0;
}

개수 제한이 50만개라 하나하나 비교하면 시간 초과가 나왔다. 더 빠른 방법을 생각해보자.

 

상한(upper bound)은 큰 수 중 첫 번째 숫자이고 하한(lower bound)는 크거나 작은 수 중에서 첫 번째 숫자를 뜻한다.

배열을 정렬한 후, 2의 상한을 찾아보면 2이고 하한은 3이다.

0 0 0 0 1 2 2 3

상한 인덱스(7)에서 하한 인덱스(5)를 빼면 2의 개수인 2개가 나온다.