Programing/Algorithm

acmicpc 수찾기: 1920

sosal 2014. 4. 30. 21:01
반응형

/*

 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;

}


}





'Programing > Algorithm' 카테고리의 다른 글

poj 2140 Herd Sums  (0) 2014.05.06
algospot - HAMMINGCODE  (0) 2014.05.06
algospot - Divisibility  (0) 2014.05.06
poj 2608 Soundex  (0) 2014.05.06
poj 2105 IP Adress  (0) 2014.04.30