1920 수 찾기

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> s;
bool binary_search(int sc, int first, int last) {
if (last - first < 2) {
for (int i = first; i <= last; i++) {
if (s[i] == sc)return true;
}
return false;
}
if (sc == s[(first + last) / 2])return true;
else if (sc > s[(first + last) / 2])return binary_search(sc, ((first + last) / 2) + 1, last);
else return binary_search(sc, first, ((first + last) / 2) - 1);
}

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

vector <int> find;
int a;
cin >> a;
for (int i = 0; i < a; i++) {
int mem;
cin >> mem;
s.push_back(mem);
}
sort(s.begin(), s.end());
cin >> a;
for (int i = 0; i < a; i++) {
int mem;
cin >> mem;
find.push_back(mem);
}
for (int i = 0; i < a; i++) {
int mem = find[i];
int mem_size = s.size()-1;
if (binary_search(mem, 0, mem_size)){
cout << "1" << "\n";
}
else cout << "0" << "\n";
}

}

선형탐색으로는 시간안에 돌릴수가 없어 이진탐색을 사용해야하는 문제이다.

처음에 이진탐색을 재귀로 작성한후 제출했는데 시간초과가 떳다.

함수 재귀호출 때문에 무거워져서 안돌아가는 줄 알고 반복문으로 돌려보았지만 시간초과였다.

 

ios_base::sync_with_stdio(0);

cin.tie(0); 메인함수 위에 이문장을 추가하고

endl ---> "\n" 이런식으로 바꿔주니

맞았습니다를 받았다.

cin cout endl이 scanf printf \n 보다 느려서 이런 차이가 생긴다고 한다