[C/C++] 백준 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) << " ";
	}

}

 

풀이 방법

ios_base::sync_with_stdio(false);
cin.tie(NULL);

입출력 속도를 빠르게 하기 위해 위의 코드를 쓰도록 합니다.

 

그리고 문제 풀이는  알고리즘 헤더(#include <algorithm>)에 존재하는
이진 탐색(Binary Serarch) 기반의 lower_bound(), upper_bound() 함수를 사용하였습니다.

lower_bound(arr, arr+N, value)

배열에서 범위내의 원소들 중 value값 보다 크거나 같은 첫번째 원소의 주소를 리턴합니다.
만약 그러한 원소가 없다면 end값을 리턴합니다.

 

upper_bound(arr, arr+N, value)

배열에서 처음으로 value값을 초과하는 원소의 주소를 반환합니다.
만약 그러한 원소가 없다면 end값을 리턴합니다.

 

따라서 해당 배열에서 원소의 개수를 찾을 때 배열을 sorting 한 후 upper_bound() - lower_bound()를 해주면 쉽게 중복된 원소의 개수를 구할 수 있습니다.

 

 

 

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2