[PS] BOJ10815 숫자카드 ( BinarySearch ) with JAVA

10815번: 숫자 카드

 

◎ 문제풀이

 

N개의 수열에 M개의 수들이 포함되어 있는지를 탐색하려고 한다. N과M은 최대 500,000으로 이중for을 이용한 탐색은 시간복잡도가 O(NM)으로 시간초과가 발생한다. 그러므로 시간복잡도를 O(MlogN)으로 줄일 수 있는 이분탐색을 해야 한다.

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//BOJ10815 숫자 카드
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] nArr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<n;i++){
            nArr[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int[] mArr = new int[m];
        st = new StringTokenizer(br.readLine());

        for(int i=0;i<m;i++){
            mArr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nArr); // 이분탐색 전 정렬하기
        for (int value : mArr) {
            if( Arrays.binarySearch(nArr, value) < 0 ) sb.append(0).append(" "); // 이분탐색
            else sb.append(1).append(" ");
        }

        System.out.println(sb.toString());
    }
}