문제

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

풀이

이분탐색

일반적인 이중 for문 방식을 이용하면, O(N^2)의 시간복잡도로 타임아웃이 발생한다. 따라서 배열을 정렬하고 나서, 이진탐색으로 key보다 큰 값이 처음 등장하는 위치 (upper_bound)에서 key 이상의 값이 처음 등장하는 위치 (lower_bound)를 빼면, 배열에서 해당 값이 등장하는 개수를 구할 수 있다.

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

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

	int n; 
	cin >> n;
	
	vector<int> arr; 
	for(int i = 0; i < n; i++){
		int val; 
		cin >> val; 
		arr.push_back(val); 
	}

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

	int m; 
	cin >> m; 

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

		// key가 arr에 없는 경우에는 upper와 lower의 위치가 동일해서 0이 출력된다. 
		int num = upper_bound(arr.begin(), arr.end(), key) - lower_bound(arr.begin(), arr.end(), key);
		cout << num << " "; 
	}

    return 0;
}

map

map 컨테이너를 이용해서 해당 값이 몇번 입력되었는지 기록한 다음에, 그 개수를 바로 출력하는 방법도 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <map> 
using namespace std;

map<int, int> m; // 0으로 초기화 

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

	int N; 
	cin >> N; 
	
	for(int i = 0; i < N; i++){
		int val; 
		cin >> val; 
		m[val]++; 
	}

	int M; 
	cin >> M; 

	for(int i = 0; i < M; i++){
		int key;  
		cin >> key; 

		cout << m[key] << " "; 
	}

    return 0;
}