C++ / 1920 / 수 찾기 ( 이분 탐색 )

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

문제 요약

n개의 정수 a[1], a[2] ... a[n]이 주어져 있을 때, 이안에 x라는 정수가 존재하는지 알아내는 프로그램을 작성해야합니다.

배열 2개를 받아 뒤에 받은 배열이 앞에 받은 배열과 똑같은 수가 있을때 1 없을 때 0이 출력 돼야 합니다.

문제 풀이

1. 기준이 될 배열을 입력 받습니다.

2. 이분 탐색할 함수를 만들어서 평가할 숫자를 입력 받아 이분 탐색 해 줍니다.

3. 이분 탐색한 결과를 bool로 받아 ( true면 있는 숫자 false면 없는 숫자 ) 0과 1을 정답배열에 넣어줍니다.

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

주의할 점

이 문제는 이분 탐색을 사용하지 않으면 시간초과가 날 수 있습니다.

이분 탐색이란 해당 값을 찾을때 리스트의 중간 값과 비교하여 해당 값이 크면 중간보다 뒤에서 다시 중간 값을 구해 비교하고, 해당 값이 작으면 중간보다 앞에서 다시 중간 값을 구해 비교하는 알고리즘입니다.

코드

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

vector<int>v1;
vector<int>v2;
vector<int>a;
int n, m;


// 이분 탐색
bool Bs(int value)
{
	int start = 0;
	int end = n - 1;

	while (start <= end)
	{
		// 나눴을때 중간 값
		int mid = (start + end) / 2;

		// 중간보다 작은경우
		if (v1[mid] > value)
		{
			end = mid-1;
		}
		// 중간 보다 큰경우
		else if (v1[mid] < value)
		{
			start = mid + 1;
		}
		// 해당 숫자인 경우
		else
		{
			return true;
		}
	}
	return false;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		v1.push_back(x);
		
	}
	sort(v1.begin(),v1.end());
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int x;
		cin >> x;
		// 입력 받으면 탐색
		if (Bs(x))
		{
			a.push_back(1);
		}
		else
		{
			a.push_back(0);
		}
	}

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

반응형

예제

5
4 1 5 2 3
5
1 3 7 9 5

결과