[BOJ/BinarySearch] 백준 2276 - 암기왕 (Java)

2276 - 암기왕

https://www.acmicpc.net/problem/2776

문제

연종이 하루 동안 본 정수들을 수첩1에 적어 놓았다.
그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종이에게 M개의 질문을 던졌다.
연종이가 봤다고 주장하는 수들을 수첩2에 적어 놓았다.

=> 수첩2에 적혀있는 순서대로, 각각의 수에 대하여 수첩1에 있으면 1/ 없으면 0 출력

입력
첫째 줄: 테스트케이스 개수 T 
수첩 1에 적어 놓은 정수의 개수 N (1 <= N <= 1,000,000)
수첩 1에 적혀 있는 정수들이 입력으로 들어옴
수첩 2에 적어 놓은 정수의 개수 M (1 <= M <= 1,000,000)
수첩 2에 적어 있는 정수들이 입력으로 들어옴
출력
수첩 2에 적혀있는 M개의 숫자 순서대로 수첩 1에 있으면 1/ 없으면 0 출력

---

풀이

이진 탐색(BinarySearch)

리스트 정렬되어 있을 때 시간복잡도 $O(log N)$

static boolean binarySearch(int[] arr, int target) {
    int lt = 0, rt = arr.length - 1;

    while (lt <= rt) {
        int mid = (lt + rt) / 2;

        if (arr[mid] == target) return true;
        else if (arr[mid] < target) lt = mid + 1;
        else rt = mid - 1;
    }

    return false;
}

---

코드

import java.io.*;
import java.util.*;

// 암기왕
public class boj_2776 {
    static boolean binarySearch(int[] arr, int target) {
        int lt = 0, rt = arr.length - 1;

        while (lt <= rt) {
            int mid = (lt + rt) / 2;

            if (arr[mid] == target) return true;
            else if (arr[mid] < target) lt = mid + 1;
            else rt = mid - 1;
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[] note1 = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                note1[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(note1);

            int M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                int target = Integer.parseInt(st.nextToken());
                sb.append(binarySearch(note1, target) ? "1\n" : "0\n");
            }
        }

        System.out.println(sb);
    }
}