[백준] - 암기왕 2776

---

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

2776번: 암기왕

---

• 입력 값이 최대 1,000,000이기 때문에 시간복잡도가 logN인 이분탐색으로 문제를 해결했다

---

[Java]

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main
{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        while(t-->0){
            ArrayList<Integer> note1 = new ArrayList<>();
            ArrayList<Integer> note2 = new ArrayList<>();

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

            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<ntSize1; i++){
                note1.add(Integer.parseInt(st.nextToken()));
            }

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

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<ntSize2; i++){
                note2.add(Integer.parseInt(st.nextToken()));
            }

            Collections.sort(note1);

            loopOut:
            for(int num : note2){
                int start = 0;
                int end = note1.size()-1;

                while(start <= end){
                    int mid = (start + end) / 2;

                    if(note1.get(mid) == num){
                        bw.write("1" + "\n");
                        continue loopOut;
                    }else if(note1.get(mid) < num)
                        start = mid+1;
                    else
                        end = mid-1;
                }
                bw.write("0" + "\n");
            }
        }



        bw.flush();
    }


}