[Baekjoon] 1920번: 수 찾기

🥅 설계

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

 

🔍 분석

수의 개수가 최대 100000개이고, 찾으려는 수의 개수가 최대 100000개이므로, 순차 탐색을 할 경우, O(10^10)으로 시간 제한을 초과한다. 따라서, 이분 탐색을 활용한다.

 

👊 풀이

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int n, m, target;
	vector<int> numbers(100001);

	bool binary_search(int target){
		int start = 0, end = n-1, mid;
		while (start <= end) {
			mid = (start+end)/2;
			if (numbers[mid] == target){
				return true;
			}
			else if (numbers[mid] < target){
				start = mid + 1;
			}
			else if (numbers[mid] > target) {
				end = mid - 1;
			}
		}
		return false;
	}

	int main() {
		cin.tie(NULL);
		ios_base::sync_with_stdio(false);
		cin >> n;
		for (int i=0; i<n; i++){
			cin >> numbers[i];
		}
		sort(numbers.begin(), numbers.begin()+n);	
		cin >> m;
		for (int j=0; j<m; j++){
			cin >> target;
			if (binary_search(target)){
				cout << 1 << "\n";
			}
			else{
				cout << 0 << "\n";
			}
		}
		return 0;
	}

 

📝 메모

• 이분 탐색을 하기 위해서는 오름차순으로 정렬되어 있어야 한다.
• numbers 배열의 크기를 100000으로 선언하고, 전체를 정렬하면, 정렬되지 않아야 할 수들까지 정렬되므로, 범위를 지정해야 한다. 범위 지정은 sort 매개변수에 시작 주소, 시작 주소+정렬하려는 원소의 개수로 전달한다.