[백준] 1920번 수 찾기

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

1920번: 수 찾기

이진탐색으로 풀어야 풀리는 문제이다.

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


int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int target;
		cin >> target;
		int start = 0; 
		int end = v.size() - 1;
		int key = -1;
		while (start <= end) {
			if (v[(start + end) / 2] == target) {
				key = (start + end) / 2;
				break;
			}
			else if (v[(start + end) / 2] > target) {
				end = (start + end) / 2 - 1;
			}
			else if (v[(start + end) / 2] < target) {
				start = (start + end) / 2 + 1;
			}
		}
		if (key == -1) cout << 0 << '\n';
		else cout << 1 << '\n';
	}
	return 0;
}

이진탐색으로 풀었더니 60ms로 성공

 

혹시나 하고 C++에 있는 find() 함수를 사용해서 풀어봤다.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int temp;
		cin >> temp;
		vector<int>::iterator iter;
		iter = find(arr.begin(), arr.end(), temp);
		if (iter != arr.end()) {
			cout << 1 << '\n';
		}
		else cout << 0 << '\n';
	}
	return 0;
}

무려 1796ms로 성공. 있는지 없는지 한 번만 찾아볼거면 굳이 정렬하는 시간을 들여서까지 이진탐색을 할 필요는 없는데 이 경우는 한 배열에서 어떤 숫자가 있는지 없는지 여러번 찾아볼 것이기 때문에 이진탐색이 훨씬 효율적이다. 정렬을 한 번만 해주면 그 후로 매우 빠르게 찾을 수 있다.