[C++] BOJ 1920 수 찾기

문제

www.acmicpc.net/problem/1920

1920번: 수 찾기

코드

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

int n, A[100001], m, num;

int search(int num) {
	int lt = 0; int rt = n;
	int mid;
	while (lt <= rt) {
		mid = (lt + rt) / 2;
		if (num == A[mid]) return 1;
		if (num > A[mid]) lt = mid + 1;
		else rt = mid - 1;
	}
	return 0;
}

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

	cin >> n;
	for (int i = 0; i < n; i++) cin >> A[i];
	sort(A, A + n);
	cin >> m;
	while (m--) {
		cin >> num;
		cout << search(num)<<'\n';
	}
}

풀이방법

이분탐색을 이용한다.

고민과정

m개의 수를 입력받을 때 배열에 입력받으려다가 굳이 배열을 만들 필요가 없다는 것을 깨달았다. 급하게 풀다가 sort를 빼먹어서 원하는 결과가 나오지 않아서 당황했다.