하루하나코딩
백준 1920 : 수 찾기 c++
HAHAKO
2023. 3. 29. 20:54
코드
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int N, M;
int nnum[100001];
int mnum[100001];
bool chk;
cin >> N;
for(int i = 0; i < N; i++){
cin >> nnum[i];
}
cin >> M;
for(int i = 0; i < M; i++){
cin >> mnum[i];
}
sort(nnum, nnum+N);
for(int i = 0; i < M; i++){
chk = false;
int low = 0;
int high = N-1;
int mid = (low+high)/2;
while(low <= high){
mid = (low+high)/2;
if(mnum[i] == nnum[mid]){
cout << "1" << "\n";
chk = true;
break;
}
else if(mnum[i] > nnum[mid]){
low = mid+1;
}
else if(mnum[i] < nnum[mid]){
high = mid-1;
}
}
if(chk == false) cout << "0" <<"\n";
}
return 0;
}
알게된 점
처음엔 그냥 처음부터 찾았는데, 시간초과가 나와서
정렬을 한다음에 이분탐색으로 찾았다.
그냥찾으면 N^2인데
정렬한다음에 이분탐색으로 찾으면 NlogN이나와서 된 것 같다.