백준 문제풀이 - 10815

개요

백준 문제 푼 내용에 대해 정리합니다.

내용

N개의 숫자와 M개의 숫자가 주어질 때, M 숫자들에 N 숫자들이 포함되어 있는지 여부를 1 또는 0으로 표현하면 되는 문제.

N, M의 숫자들을 int 배열에 각각 저장하였고 이후 M 숫자들을 arr 배열에 저장하였다. for 문을 돌며 arr 배열의 i 번째 원소를 N 숫자를 저장한 배열과 비교해 여부를 체크하였다.

구체적으론 IntStream 의 anyMatch 함수를 사용하였는데, 문제 조건에 의하면 최대 백만 개를 탐색할 수 있고 시간 제한은 2초이므로, for 문안에서 각 원소를 탐색하는 것은 Big O(n^2) 을 만들어내 시간 초과라는 결과를 내었다.

public class Main {

    public static int i = 0;

    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 arr[] = new int[N];

        String N_number = br.readLine();

        String N_arr[] = N_number.split(" ");

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(N_arr[i]);
        }

        Integer[] arr1_1 = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        Arrays.sort(arr1_1, Collections.reverseOrder());

        int M = Integer.parseInt(br.readLine());
        int arr2[] = new int[M];

        String M_number = br.readLine();

        String M_arr[] = M_number.split(" ");

        for(int i = 0; i < M; i++) {
            arr2[i] = Integer.parseInt(M_arr[i]);
        }

        String result = "";
        for(i = 0; i < M; i++) {
            if(IntStream.of(arr).anyMatch(x -> x == arr2[i])) {
                result += "1 ";
            } else {
                result += "0 ";
            }
        }

        result = result.trim();

        System.out.println(result);
    }
}

그래서 해당 문제에 대해 어떻게 풀지 고민하다가 답을 구글링 한 결과 이분 탐색을 사용하면 시간 초과에 걸리지 않고 풀 수 있다는 것을 알 수 있었다.

 

이분 탐색

이분 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이때 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.

 

코드

그래서 아래와 같이 코드를 짜서 제출한 결과 통과할 수 있었다.

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];

        String N_number = br.readLine();

        String N_arr[] = N_number.split(" ");

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(N_arr[i]);
        }

        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        int arr2[] = new int[M];

        String M_number = br.readLine();

        String M_arr[] = M_number.split(" ");

        for(int i = 0; i < M; i++) {
            arr2[i] = Integer.parseInt(M_arr[i]);
        }

        int result[] = new int[M];

        for(int i = 0; i < M; i++) {
            int right = N - 1;
            int left = 0;
            while(left <= right) {
                int mid = (right + left) / 2;
                if(arr[mid] == arr2[i]) {
                    result[i] = 1;
                }

                if(arr[mid] > arr2[i]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }

        for(int i = 0; i < M; i++) {
            System.out.print(result[i] + " ");
        }
    }
}

 

결과