백준_1920: 수 찾기

 

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

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

int main() {

	int n, m;
	vector<int>mv, nv, answer;

	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> m;
		nv.push_back(m);
	}
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> m;
		mv.push_back(m);
	}
	
	sort(nv.begin(), nv.end());	//nv배열 오름차순 정렬
	
	int low = 0, high = nv.size() - 1, mid;

	for (int i = 0; i < mv.size(); i++) {
		while (true) {	//이분탐색
			mid = (low + high) / 2;
			if (mv[i] == nv[mid]) {	//키값 찾았을 때
				answer.push_back(1);
				break;
			}
			else if (mv[i] < nv[mid])	//mid값보다 작을때
				high = mid - 1;
			else if (mv[i] > nv[mid])	//mid값보다 클때
				low = mid + 1;
			if(low > high){				//키값 없을 때
				answer.push_back(0);
				break;
			}
		}
		low = 0, high = nv.size() - 1;	//low, high값 초기화
	}

	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << "\n";

	system("pause");
	return 0;
}