완전 탐색을 통해 해결하려고 하면 최대 (500,000 * 20,000,000)번 탐색을 하게된다.
이 경우 시간 초과가 일어나기 때문에 이분탐색을 사용해서 해결하는 것이 대표적이다.
조심할 부분은 이분탐색 시에는 반드시 정렬이 되어 있어야 한다는 점이다.
이분탐색 문제에서도 기초 문제여서 간단하게 해결할 수 있었다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int[] numCard = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i=0;i<n;i++){
numCard[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(numCard);
int m = Integer.parseInt(br.readLine());
int[] checkCard = new int[m];
st = new StringTokenizer(br.readLine()," ");
for(int i=0;i<m;i++){
checkCard[i] = Integer.parseInt(st.nextToken());
sb.append(binarySearch(checkCard[i],0,n-1,numCard)).append(" ");
}
System.out.println(sb);
}
public static int binarySearch(int m,int min,int max,int[] arr){
while(min<=max){
int mid = (min+max)/2;
if(arr[mid]==m){
return 1;
}
else if(m<arr[mid]){
max = mid-1;
}
else{
min = mid+1;
}
}
return 0;
}
}