C++ / 10816 / 숫자 카드 2 ( 이분 탐색 )

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

문제 요약

n개의 숫자카드와 m개의 정수가 있을때, 이 수가 적혀있는 숫자 카드를 몇개 가지고 있는지 구해야 합니다.

문제 풀이

1. 카드를 입력 받습니다.

2. 원활한 탐색을 위해 입력받은 카드를 오름차순으로 정렬해 줍니다.

3. 탐색 함수를 만듭니다. 함수 내에서는 upper_bound ( 해당 숫자가  마지막으로 들어있는  주소 )와 lower_bound ( 해당 숫자가 처음으로 나온 주소 )의 차로 카드 내에서 숫자가 몇개 있는지 계산해서 반환 합니다.

4. 정수를 입력받고 입력 받은 정수를 탐색하여 정답 배열에 저장합니다.

5. 정답 배열을 출력합니다.

 

주의할 점

이 문제는 이분 탐색문제입니다. 단순 반복문으로 찾을려고 하면 틀릴 수 있습니다.

 

처음엔 일반적인 이분탐색 알고리즘에서 원하는 숫자를 발견시 인덱스를 제거하고 다시 탐색하도록 하였는데,

그렇게 하니 무한 루프에 빠지는 문제가  발생하였습니다.

그래서 훨씬 간단한 upper_bound, lower_bound를 사용해서 풀었습니다.

https://lgj415415.tistory.com/69

 

 

코드

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

int n, m;
int sum = 0;
vector<int>v1;
vector<int>v2;


int bs(int x)
{
	return (upper_bound(v1.begin(), v1.end(), x) - v1.begin()) - (lower_bound(v1.begin(), v1.end(), x) - v1.begin());
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v1.push_back(a);
	}
	sort(v1.begin(), v1.end());

	cin >> m;
	for (int i = 0;i < m; i++)
	{
		int a;
		cin >> a;
		v2.push_back(bs(a));
	}

	for (int i = 0; i < m; i++)
	{
		cout << v2[i] << " ";
	}

	return 0;
}

반응형

예제

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

결과