[Binary Search/자바] 백준 1920. 수 찾기

1920번: 수 찾기

이 문제는 시간제한을 봤을 때, O(N^2)으로는 풀 수 없다. 즉, 일반적으로 우리가 떠올릴 수 있는 이중 반복문을 이용할 수 없다는 의미이다.

 

이렇게 시간복잡도를 고려할 때, 일반적으로 좋은 성능을 보여주는 것이 이진 탐색이다.

public class B1920 {
    static int n, m;
    static int[] arr;
    static int[] ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            boolean find = false;
            int target = Integer.parseInt(st.nextToken());
            int start = 0;
            int end = arr.length - 1;
            while (start <= end) {
                int mid_idx = (start + end)/2;
                int mid_val = arr[mid_idx];
                if (mid_val > target) {
                    end = mid_idx - 1;
                } else if (mid_val < target) {
                    start = mid_idx + 1;
                } else {
                    find = true;
                    break;
                }

            }
            if (find) {
//                bw.write(Integer.toString(1));
                System.out.println(1);
            } else {
//                bw.write(Integer.toString(0));
                System.out.println(0);
            }
//            bw.flush();
            br.close();
//            bw.close();
        }

    }
}

아직 BufferedWriter가 익숙치 않아서 적용에 실패했는데, 큰 문제는 아닐 것 같아서 우선 주석 처리하고 sout으로 해결했다. 나중에 한번 알아봐야겠다.