[백준] 10816번: 숫자 카드 2 [C++]

 

알고리즘 분류: 자료 구조, 정렬, 이분 탐색, 해시를 사용한 집합과 맵

문제 링크: https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

【 문제 】

 

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

 

 

【 입력 】

 

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 <= N <= 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 <= M <= 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

 

【 출력 】

 

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

 

 

【 풀이 】

 

수들을 입력받은 다음 찾고자 하는 특정 수가 몇 개 있는지를 출력하는 문제이다.

50만 개, 50만 개씩 배열에 수들을 넣은 다음 선형 탐색을 하면 시간 복잡도가 O(N^2)로

제출 시 시간 초과가 나온다.

 

이는 평균 시간 복잡도가 O(logN)인 이분 탐색을 이용하면 된다.

이분 탐색 기반인 upper_bound와 lower_bound을 사용하면 간단히 해결 가능하다.

• upper_bound: 찾고자 하는 값의 다음 값이 최초로 나타나는 위치
• lower_bound: 찾고자 하는 값보다 같거나 큰 값이 최초로 나타나는 위치

예를 들어, [ 3 5 5 6 7 7 8 8 9 ] 가 저장된 배열 arr 이 있고, 7의 개수를 찾고 싶다고 하자.

 

lower_bound(arr, arr+9, 7): 4 (7 이상 값이 처음 나오는 위치)

upper_bound(arr, arr+9, 7): 6 (7보다 큰 값이 처음 나오는 위치)

 

두 인덱스 값을 빼주면 찾고자 하는 값의 개수를 구할 수 있다.

 

 

 

【 코드 】

 

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

vector<int>cards;
vector<int>card_comp;

int main(void)
{
	int n, m;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		cards.push_back(num);
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int num;
		cin >> num;
		card_comp.push_back(num);
	}

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

	for (int i = 0; i < m; i++)
	{
		cout <<
			(upper_bound(cards.begin(), cards.end(), card_comp[i]) - cards.begin()) -
			(lower_bound(cards.begin(), cards.end(), card_comp[i]) - cards.begin()) 
			<< ' ';
	}

	return 0;
}