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

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

문제 요약

숫자 카드는 정수 하나가 적혀져 있는 카드입니다. 상근이는 숫자 카드 N개를 가지고 있습니다. 정수가 M개 주어졌을 때, 이 수가 적혀있는 숫자카드를 상근이가 가지고 있는지 아닌지를 구하는프로그램을 작성해야합니다.

문제 풀이

1. 비교할 카드 배열을 입력받습니다. 이 카드배열은 이분탐색을 해야하기 때문에 정렬 해줍니다.

2. 비교 당할 카드 배열을 입력받습니다.

3. 이분탐색 함수를 만듭니다. start end mid 값을 만들어서 초기값으론

start = 0

end = 비교할배열크기

mid = end/2

을 줍니다.

4. while 문을돌리는데 mid 값은 매 회차마다 (start + end) / 2로 초기화 해줍니다.

5. 비교 문으로 찾으려는 값이 mid보다 클경우 start를 mid 다음인덱스로 합니다. mid보다 작을 경우는 end를 mid 전 인덱스로 합니다.

6. 회차를 돌리다 보면 mid와 찾는 값이 같아지게 되는데 이때는 1을 반환합니다.

7. mid가 배열 size를 넘어갈때 까지 찾지 못하거나 start가 end값을 넘어버리면 while문을 끝내고 0을 반환합니다.

8. 비교 당할 카드배열을 이분탐색 시킵니다.

주의할 점

간단한 이분탐색 문제여서 바로 맞출줄 알았는데 방심해서 실수를 했습니다.

탐색을 하다보면 mid값이 벡터 배열의 범위를 넘어갈때 생기는데 이때 오류가 발생합니다.

5
1 2 3 4 5
5
3 4 5 6 7

위 예제를 돌리면 없는 배열을 접근함

 

따라서 배열의 크기를 넘어가면 break 해주어야 합니다.

코드

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

long long int n, m;

vector<long long int>v1;
vector<long long int>v2;


int bs(int x)
{
	int start = 0;
	int end = v1.size();
	int mid = end/2;
	while (start <= end)
	{
		mid = (end + start) / 2;
        // 배열 사이즈 넘어가면 브레이크
		if (mid >= v1.size())
		{
			break;
		}
		if (v2[x] > v1[mid])
		{
			start = mid + 1;
		}
		else if (v2[x] < v1[mid])
		{
			end = mid - 1;
		}
		else
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int a;
		cin >> a;
		v1.push_back(a);
	}
	sort(v1.begin(), v1.end());
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v2.push_back(a);
	}
	for (int i = 0; i < n; i++)
	{
		cout << bs(i) << " ";
	}


	return 0;
}

반응형

예제 1

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

결과 1

예제 2

5
1 2 3 4 5
5
3 4 5 6 7

결과 2