문제 이해

숫자 배열이 주어진다.
이 때 해당 배열에 특정 숫자가 존재하면 1을, 존재하지 않으면 0을 출력한다.

---

문제 풀이

최대 100000개의 숫자가 주어지고, 확인해야 할 특정 숫자는 최대 100000개이다.
따라서 Brute-Force로 할 경우 매우 나쁜 성능을 가지게 될것이다.

이분 탐색을 통해 해당 숫자가 존재하는지 아닌지를 확인하였다.

---

코드

import java.util.*;

public class Main {
	static int[] A;
	static int N;

	static Integer bin_search(int left, int right, int value) {
        // 이분 탐색 함수
		int mid;
		while(left <= right) { // 종료 조건 : left > right
			mid = (left + right)/2;
			if(A[mid] > value) {
                // 중간값이 value보다 크다.
                // 중간값보다 작은 값을 확인하면 되므로 right = mid-1로 
                // 설정해준다.
				right = mid  - 1;
			}
			else if(A[mid] <value) {
                // 중간값이 value보다 작다.
                // 따라서 중간값보다 큰 값을 확인하면 되므로 left = mid-1로 
                // 설정해준다.
				left = mid + 1;
			}
			else {
                // 중간값이 같다
                // 즉, 특정 수가 존재하기 때문에 1을 반환해준다.
				return 1;
			}
		}
        // while문을 빠져나왔다는 것은 중간값이 같은 경우가 없다는 의미이다.
        // 따라서, 특정 수는 존재하지 않는다는 의미이므로 0을 반환해준다.
		return 0;
	}
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		A = new int[N];
		
		for(int i = 0;i<N;i++) {
			A[i] = sc.nextInt();
		}
		int M = sc.nextInt();
		Arrays.sort(A); 
        // 매우 중요한 부분. 이분 탐색을 하기 위해서는 무조건 정렬을 우선시해주자

		StringBuilder sb = new StringBuilder();
		for(int i =0;i<M;i++) {
			int k = sc.nextInt();
			sb.append(bin_search(0,N-1,k)+"\n");
		}
		System.out.println(sb.toString());
	}
}

---

결과