10815번: 숫자카드

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

이 문제를 아래의 코드와 같이 for문 돌려막기로 풀면 시간초과가 뜬다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int[] N= new int[n];
		for(int i=0;i<n;i++) {
			N[i]=scan.nextInt();
		}
		
		int m=scan.nextInt();
		int[] M= new int[m];
		for(int i=0;i<m;i++) {
			M[i]=scan.nextInt();
		}
		
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(M[i]==N[j]) {
					M[i]=1;
					break;
				}
				else if(M[i]!=N[j]&&j==n-1) {
					M[i]=0;
				}
			}
		}
		
		for(int i=0;i<m;i++) {
			System.out.print(M[i]+" ");
		}
	}
}

그러면 어떻게 풀어야하나?

1. 상근이가 가진 카드를 작거나 큰 순서대로 정렬한다.
2. 이진 탐색을 이용해 상근이가 가진 카드 중 해당하는 카드가 있는지 탐색한다.

정렬과 이진 탐색을 써야하는 것이다.
나는 머지 소트를 사용했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	//Merge Sort
	private static void mergeSort(int[] arr) {
		int[] tmp= new int[arr.length]; 
		mergeSort(arr,tmp,0,arr.length-1);
	}
	
	private static void mergeSort(int[] arr,int[] tmp,
			int start,int end) {
		if(start<end) {
			int mid= (start+end)/2;
			mergeSort(arr,tmp,start,mid);
			mergeSort(arr,tmp,mid+1,end);
			merge(arr,tmp,start,mid,end);
		}
	}
	
	private static void merge(int[] arr,int[] tmp, int start,
			int mid,int end) {
		for(int i=start;i<=end;i++) {
			tmp[i]=arr[i];
		}
		int part1=start;
		int part2=mid+1;
		int index=start;
		while(part1<=mid&&part2<=end) {
			if(tmp[part1]<=tmp[part2]) {
				arr[index]=tmp[part1];
				part1++;
			}else {
				arr[index]=tmp[part2];
				part2++;
			}
			index++;
		}
		for(int i=0;i<=mid-part1;i++) {
			arr[index+i]=tmp[part1+i];		
		}
	}

	// 이진 탐색
	private static int binarySearch(int[] arr,int goal) {
		int low=0;
		int high=arr.length-1;
		
		while(high>=low){
			int mid=(low+high)/2;
			
			if(goal==arr[mid]) {
				return 1;
			}else if(goal<arr[mid]) {
				high=mid-1;
			}else {
				low=mid+1;
			}
		}
		return 0;
	}
    
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		//입력 값 받기
		StringTokenizer st;
		int n=Integer.parseInt(br.readLine());
		int[] N= new int[n];
		for(int i=0;i<n;i++) {
			st= new StringTokenizer(br.readLine());
			N[i]=Integer.parseInt(st.nextToken());
		}
		
		mergeSort(N); // 머지소트 
        
		int mid = N.length/2;
		int m=Integer.parseInt(br.readLine());
		int[] M= new int[m];
		for(int i=0;i<m;i++) {
			st= new StringTokenizer(br.readLine());
			M[i]=Integer.parseInt(st.nextToken());
		}
		
		
		for(int i=0;i<m;i++) {
			if(binarySearch(N,M[i])==1) { //이진 탐색
				M[i]=1;
			}
			else {
				M[i]=0;
			}
		}
		for(int i=0;i<m;i++) {
			bw.write(M[i]+" ");
		}
			bw.close();
		br.close();
	}
}