[백준] Class2-수 찾기 C++ 1920번

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

1
1
0
0
1

 

처음 소스코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//정수의 범위는 -2^31~2^31 => long 사용
int n;	//n개의 자연수
long k[100001];
int m;
long p[100001];
bool isNone = false;

void cmp()
{
	for (int i = 0; i < m; i++)	//m, p
	{
		isNone = true;
		for (int j = 0; j < n; j++)	//n, k
		{
			if (p[i] == k[j])
			{
				cout << 1 << "\n";	//같으면 한번만 1 출력
				isNone = false;
			}
		}
		if (isNone == true)
			cout << 0 << "\n";
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (long i = 0; i < n; i++)
	{
		cin >> k[i];
	}

	cin >> m;
	for (long i = 0; i < m; i++)
	{
		cin >> p[i];
	}

	cmp();

	return 0;
}

최종 소스코드:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool binary_tree(vector<int>& A, int t);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<int> A(N);
	for (int i = 0; i < N; i++) 
	{
		cin >> A[i];
	}

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

	int M;
	cin >> M;

	for (int i = 0; i < M; i++) 
	{
		int target;
		cin >> target;
		cout << binary_tree(A, target) << "\n";
	}
}

bool binary_tree(vector<int>& A, int t) 
{
	int start = 0;
	int end = A.size() - 1;

	while (start <= end) 
	{
		int mid = (start + end) / 2;
		int value = A[mid];

		if (value == t)
			return true;
		else if (value < t)
			start = mid + 1;
		else
			end = mid - 1;
	}

	return false;
}

접근방법: 시간 초과되는 문제를 이진탐색(이분탐색) Binary search을 사용해서 시간을 줄여야 풀 수 있는 문제이다.