[백준 2776 / 암기왕 / JAVA / 이분 탐색]

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

2776번: 암기왕

 

문제 접근

출력 시간 때문에 StringBuilder 활용

 

List에 노트1의 숫자들을 저장 후 정렬

이후 M 크기의 노트2 숫자들을 검사하는 반복문 실행

입력한 값보다 노트1 인덱스의 숫자가 크면 더 작은 값을 탐색하기 위해 right 감소

숫자가 작으면 더 큰 값을 탐색하기 위해 left 증가

같다면 1을 StringBuilder에 저장, 다르다면 0을 저장하고 반복문 종료 후 저장한 StringBuilder 출력

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

public class Main {
	public static void main(String[] args) throws IOException {
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   StringTokenizer st;
	   
	   int T = Integer.parseInt(br.readLine()); // 테케
	   
	   for(int t=0; t<T; t++){
		   StringBuilder sb = new StringBuilder();
		  int N = Integer.parseInt(br.readLine()); // 수첩1
		  
		  List<Integer> note1 = new ArrayList<Integer>();
		  st = new StringTokenizer(br.readLine());
		  for(int i=0; i<N; i++) note1.add(Integer.parseInt(st.nextToken()));
		  Collections.sort(note1);
		  
		  int M = Integer.parseInt(br.readLine()); // 수첩2
		  st = new StringTokenizer(br.readLine());

		  for(int i=0; i<M; i++) {
				  
				  int left = 0;
				  int right = note1.size()-1;
				  int mid = 0;
				  int temp = Integer.parseInt(st.nextToken());
				  
				  while(left <= right) {
					  mid = (left + right) / 2;
				  
				  if(note1.get(mid) > temp) {
					  right = mid -1;
				  }
				  else if(note1.get(mid) < temp) {
					  left = mid + 1;
				  }
				  else if(note1.get(mid) == temp) {
					  sb.append("1").append("\n");
					  break;
				  }
			  }
				if(note1.get(mid) != temp)  sb.append("0").append("\n");
		  }
		  System.out.print(sb);
	   }
	}
}