문제번호

1920

import java.util.*;

public class Main {
	
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		StringBuilder sb = new StringBuilder();
		
		// 시도횟수
		int N = in.nextInt();
		
		int A [] = new int [N];
		
		// input 1 
		for (int i = 0 ;i < A.length; i++) {
			A[i] = in.nextInt();
		}
		Arrays.sort(A);
		
		int M = in.nextInt();
	
		int mArr [] = new int [M];
	
		// input 2
		for (int i = 0 ;i < mArr.length; i++) {
			mArr[i] = in.nextInt();
		}		
		
		
		for (int i = 0 ;i < mArr.length; i++) {
			if (Bsearch(A,mArr[i]) == -1)
				sb.append(0 + "\n");
			else
				sb.append(1 + "\n");
		}
	
		System.out.println(sb);
	}
	
	static int Bsearch (int[] arr , int value ) {
	
		int preIndex = 0;
		int postIndex = arr.length-1;
		
		while (preIndex <= postIndex) {
			int mid = (preIndex + postIndex) /2;
			
			if (value > arr[mid]) 
				preIndex = mid +1;
			
			else if (value < arr[mid]) 
				postIndex = mid -1;
			
			else 
				return mid;
			
		}
		
		return -1;
	}
	
}

문제

A의 배열 과 A의 배열원소, B의 배열과 B의 배열원소를 비교하여 A의 배열에 B의 원소가 있는경우 1 아닌경우 0을 출력한다.

풀이

일반적인 탐색방식을 사용하면 시간초과가 발생함으로 2진탐색을 사용하여 풀어야한다.

TLI

직접 구현하여 사용해도 되고 자바에서 Binarysearch 가 있다. 이를 활용하여 사용해도 된다.