10816: 숫자 카드 2

-Class2 : Silver4

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

10816번: 숫자 카드 2

 

-결과

 

-코드

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

int N, M, x;
int card[500001];


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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> card[i];
	
	sort(card, card + N);

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> x;
		cout << upper_bound(card, card + N, x) - lower_bound(card, card+N, x) << " ";
	}

}

 

-풀이

이 문제는 이진탐색의 lower_bound(), upper_bound() 함수를 사용한다.

lower_bound()는 정렬된 수들 중 찾고자 하는 k 이상의 최초값의 index를 찾는 함수이고

upper_bound()는 정렬된 수들 중 찾고자 하는 k를 초과한 최초값의 index를 찾는 함수이다.

배열을 sort하고 upper_bound() - lower_bound()를 해서 중복된 원소의 개수를 구한다.