[코딩테스트] 백준 1920 수 찾기 -C++

문제 풀이

• 문제는 다음과 같은 조건을 가진다.
  X배열이 주어지고 A 배열에 x 각각의 수가 존재하는지 0과 1로 출력
• 결국 X[i] 값이 A배열에 있는지 탐색을 하는 탐색 문제로 볼 수 있다.
• 쉽게 구현할 수 있는 선형 탐색으로 구현할 경우,
  최대 100,000 개를 가지는 N과 M으로 인해 O(N^2)를 가지게 되어 시간 초과가 날 것이다.
• 따라서 O(nlogn)을 가지는 이진 탐색 으로 접근 해야한다.
  이진 탐색 구현 방법
  1. 탐색할 배열의 left = 0 와 right = N으로 초기화 한다.
  2. 탐색을 모두 한 경우는 left > right 된 경우이다. while 문의 조건으로 left <=right
  3. 이진 탐색은 mid값을 탐색하며 줄여나가는 것이므로 mid = (left+right)/2
  4. A[mid]값과 찾고자하는 값 과의 비교
• 처음 vector로 구현하였는데 시간 초과가 났다. 대량의 데이터를 다룰 때는 동적 배열로 구현하자.

C++ 코드

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

//arr에서 n을 찾고자 한다. N은 arr의 크기 
void binary_search(int* arr,int n,int N ) {
	int left = 0; 
	int right = N ;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] > n) { 
			right = mid - 1; 
		}
		else if (arr[mid] < n) {
			left = mid + 1;
		}
		else {//일치하는 경우 
			cout << "1\n";
			return;
		}
	}
	cout << "0\n";
	return; 
}

int main() {
	//-2^31 보다 크거나 같고 2^31보다 작다. 
	int N, M;
	int* A;
	int* X; 

	cin >> N; 
	A = new int[N];

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

	cin >> M; 
	X = new int[M];

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

	//알고리즘 헤더 sort의  시간 복잡도 nlog n 
	//vector begin이 시간초과를 초래하는 듯하다. 
	//vector에서 동적 배열로 고쳐서 시간 초과는 막았다. 
	sort(A,A+N);

	for (int i = 0; i < M; i++) {
		binary_search(A, X[i], N);
	}

	return 0;
}