BOJ 1920: 수 찾기

✔ 문제 링크

백준 1920: 수 찾기

✔ 문제해결전략

• 이진탐색

✔ Code 1) binary search 직접 구현

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int target, vector<int>& vec, int len) {
	int front = 0;
	int end = len - 1;
	
	while(front <= end) {
		int mid = (front + end) / 2;
		if(vec[mid] > target) end = mid - 1;
		else if(vec[mid] < target) front = mid + 1;
		else return 1;
	}
	return 0;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	vector<int> num;
	
	cin >> n;
	num.resize(n);
	for(int i=0;i<n;i++) cin >> num[i];
	
	sort(num.begin(), num.end());
	int len = num.size();
	
    	cin >> m;
	for(int i=0;i<m;i++) {
		int t;
		cin >> t;
		cout << binarySearch(t, num, len) << "\n";
	}
}

✔ Code 2) std::binary_search 사용

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	vector<int> num;
	
	cin >> n;
	num.resize(n);
	for(int i=0;i<n;i++) cin >> num[i];
	
	sort(num.begin(), num.end());
	
    	cin >> m;
	for(int i=0;i<m;i++) {
		int k;
		cin >> k;
		cout << binary_search(num.begin(), num.end(), k) << "\n";
	}
}

✔ Comment

문제에서 이진 탐색 사용하라고 외치고 있다. std::sort가 nlog(n)이고 binary search가 log(n)인데 m번 하니까 mlog(m) 총 nlog(n) + mlog(n).

✔ Check Point

• while문 조건에 등호 안 넣으면 제대로 동작하지 않는다. front == end인 경우도 생각해 주어야 한다. mid == front == end 우선 된 다음 end가 작아지던지 front가 커지던지 해서 while문 탈출한다

• STL binary_search는 오름차순 정렬되어 있을 때만 사용할 수 있다