[백준 알고리즘 c++] 문제 10. 벡터를 이용한 데이터 다루기 백준 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을 출력한다.

내 풀이 )

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

using namespace std;

int main()
{
	//문제 : n개의 정수중 x라는 정수의 존재여부를 파악
	//입력 :
	// 1. 벡터 길이를 입력한다.
	// 2. 백터에 담을 요소를 입력한다.
	// 3. 비교할 벡터의 길이를 입력한다.
	// 4. 비교할 벡터에 담을 요소를 입력한다.
	//처리 :
	// 기존 벡터와 비교할 벡터의 요소를 비교한다.
	//출력 :
	// 같은 요소면 1, 다른 요소면 0을 출력한다.

	int vec_input = 0;
	cin >> vec_input;

	vector<int> vec(vec_input); //벡터에 갯수 부여

	for (int i = 0; i < vec_input; i++)
	{
		int vec_input_number = 0;
		cin >> vec_input_number;

		vec.push_back(vec_input_number);
	}
	
	//binary_search는 순차배열만 사용가능하다.그러므로 sort로 정렬해준다.
	sort(vec.begin(), vec.end());
	

	int vec_input2 = 0;
	cin >> vec_input2;
	for (int i = 0; i < vec_input2; i++)
	{
		int vec_input_number = 0;
		cin >> vec_input_number;

		if (binary_search(vec.begin(), vec.end(), vec_input_number))
		{
			cout << 1 << "\n";
		}
		else
		{
			cout << 0 << "\n";
		}
	}


	return 0;
}

문제점 : endl;을 사용하면 시간복잡도가 오래걸린다. "\n"로 바꿔서 사용한다.

추가로 binary_search를 구현해서 사용할수 있다.

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

int array1[100000] = { 0 };

bool isExist1(int s, int e , int num)
{

	int m = (s + e) / 2;

	if (s >= e)
	{
		return false;
	}

	if (array1[m] == num)
	{
		return true;
	}

	if (array1[m] < num)
	{
		s = m + 1;
	}
	else
	{
		e = m;
	}

	isExist1(s,e,num);

}

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

	int M;
	int N;
	cin >> N;

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

	sort(array1, array1+N);

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;

		bool isExist = false;
		int s = 0, e = N;
		while (s < e)
		{
			//중간 지점 구하고
			int m = (s + e) / 2;
			//비교하고
			if (array1[m] == num)
			{
				isExist = true;
				break;
			}

			//그거에 따라서 범위 조정
			if (array1[m] < num)
			{
				s = m + 1;
			}
			else
			{
				e = m;
			}
		}

		cout << (isExist ? "1\n" : "0\n");
	}


}