백준 10815번: 숫자 카드

백준 10815번: 숫자 카드

 

-선형 탐색법(Linear Search)을 사용하면 시간 제한을 지키지 못하므로 이진 탐색법(Binary Search)을 사용해야 됩니다.

-이진 탐색법을 사용하기 위해서는 오름차순으로 정렬되어 있어야 하므로 퀵소트(QuickSort)를 이용합니다.

 

	import java.util.Scanner;
	public class Main {
	public static void quicksort(int[] a){
	sort(a, 0, a.length-1);
	}
	public static void sort(int[] a, int low, int high){
	if(low >= high) return;
	int mid = partition(a, low, high);
	sort(a, low, mid-1);
	sort(a, mid, high);
	}
	private static int partition(int[] a, int low, int high){
	int pivot = a[(low + high) / 2];
	while(low <= high){
	while(a[low] < pivot) low++;
	while(a[high] > pivot) high--;
	if(low <= high) {
	swap(a, low, high);
	low++;
	high--;
	}
	}
	return low;
	}
	private static void swap(int[] a, int i, int j){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static int binarySearch(int[] a, int target){
	int low = 0;
	int high = a.length-1;
	int mid;
	while(low <= high){
	mid = (low+high) / 2;
	if(a[mid] == target)
	return mid;
	else if(a[mid] > target)
	high = mid - 1;
	else
	low = mid + 1;
	}
	return -1;
	}
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n];
	for(int i = 0; i < n; i++){
	a[i] = sc.nextInt();
	}
	quicksort(a);
	int m = sc.nextInt();
	int[] b = new int[m];
	for(int i = 0; i < m; i++){
	b[i] = sc.nextInt();
	}
	for(int i = 0; i < m; i++){
	int tf = binarySearch(a, b[i]);
	if(tf == -1)
	System.out.print("0 ");
	else
	System.out.print("1 ");
	}
	sc.close();
	}
	}

view raw BOJ_10815.java hosted with ❤ by GitHub