acmicpc 수찾기: 1920

/*

 * http://sosal.tistory.com/
 * made by so_Sal
 */

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

문제

  N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

  첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

출력

  M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력

5

4 1 5 2 3

5

1 3 7 9 5

예제 출력

1

1

0

0

1

있으면 1, 없으면 0이니까 첫번째로 입력된 자연수들을 sorting 하고나서

두번째 입력된 숫자 하나하나가 첫번째 배열에 존재하는지 binary search로 검색하면 됩니다.

단순 검색 or 정렬하더라도 n검색으로는 시간초과가 뜨네요..

#include<iostream>

#include<vector>

#include<algorithm>

#include<iomanip>

#include<string>

using namespace std;

int main(void){//32빼면 대문자로 바뀜

int c,c1;

int tmp;

vector<int> arr;

vector<int> find;

        //arr: 첫번째 입력시퀀스, find: 두번째 입력시퀀스

cin>>c;

for(int i=0;i<c;i++){

cin>>tmp;

arr.push_back(tmp);

}

cin>>c1;

for(int i=0;i<c1;i++){

cin>>tmp;

find.push_back(tmp);

}/////////////////입력

sort(arr.begin(), arr.end()); //첫번째 시퀀스 정렬

for(int i=0;i<c1;i++){

int count = 0;

if(binary_search(arr.begin(), arr.end(), find[i])) //이진탐색

cout<<1<<endl;

else

cout<<0<<endl;

}

}