백준[10815]번 : 숫자 카드 ( JAVA )

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

10815번: 숫자 카드

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
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 n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] ar = new int[n];
		
		for(int i=0;i<n;i++) {
			int t = Integer.parseInt(st.nextToken());
			ar[i] = t;
		}
		
		Arrays.sort(ar);
		
		int m = Integer.parseInt(br.readLine());
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		int[] ar2 = new int[m];
		
		for(int i=0;i<m;i++) {
			int t = Integer.parseInt(st1.nextToken());
			int ans = Binary(t,ar);
			if(ans == 1) { // 있는 경우
				ar2[i] = 1;
			}
			else { // 없는 경우
				ar2[i] = 0;
			}
		}
		
		for(int i=0;i<m;i++) { // 출력
			bw.write(ar2[i]+" ");
		}
		
		br.close();
		bw.close();
	}
	
	static int Binary(int a,int[] ar){ // 이분탐색
		int left = 0;
		int right = ar.length-1;
		
		while (left <= right) {
			int mid = (left + right) / 2;
			
			if (a < ar[mid]) {
				right = mid-1;
			} 
			else if (a > ar[mid]) {
				left = mid+1;
			}
			else {
				return 1; // 있다면 1 반환
			}
		}
		
		return 0; // 없다면 0 반환
	}
}

---

이분탐색 문제인지 모르고 ArrayList로 풀었는데 시간초과가 났다.

문제 밑 알고리즘 분류에 이분탐색을 보고 바로 풀었다.