BOJ_18809 [ 수 찾기 ]

문제

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

1920번: 수 찾기

 

문제 해결 방법

이분탐색을 이용하면 해결할 수 있는 문제이다.

1. stl 함수 사용 

c++ 에서 제공하는 binary_search() 함수를 사용하면 해결 (algorithm.h 헤더파일 추가해주세요.)

 

2.직접 구현을 했을때

문제를 제출 했을 때 시간초과가 계속 나서 원인을 찾아보니

 

if( arr[mid]<find_num) 이라면

left = mid+1 

else if( arr[mid] >find_num) 이라면

right = mid-1 

 

해주어야 되는데 right 값을 변경할 때 -1을 안해주어서 시간초과가 발생했다...

라이브러리 함수를 사용하는 것도 중요하지만 직접 구현해서 내부 로직이 어떤식으로 동작하는 아는 것을 추천드립니다.

소스 코드

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/BinarySearch/boj_1920.cpp

jokerKwu/BOJ_Algorithm

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
typedef long long ll;
vector<ll> arr;

int binarySearch(ll findNum) {
	int left = 0, right = arr.size()-1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] == findNum) {
			return 1;
		}
		else if (arr[mid] > findNum) {
			right = mid-1;	//-1 하고 안하고 시간초과
		}
		else {
			left = mid + 1;
		}
	}
	return 0;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		ll num;
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	cin >> M;
	for (int i = 0; i < M; i++) {
		ll num;
		cin >> num;
		cout<<binarySearch(num)<<'\n';
		//cout << binary_search(arr.begin(), arr.end(), num)<<'\n';	//라이브러리 함수 사용
	}

	return 0;
}