[백준] 10815 숫자 카드_ JAVA

● 문제

 

---

● 풀이

 

첫 번째 풀이의 코드

 

이는 선형 탐색으로 인해 시간초과가 발생하였다. 'arrayList.contains()' 메서드는 리스트를 순차적으로 탐색하여 원하는 값이 있는지 확인하기에 탐색 시간이 O(n)이 소요된다.

 

import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        ArrayList<Integer> arrayList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            arrayList.add(in.nextInt());
        }
        int m = in.nextInt();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < m; i++) {
            if(arrayList.contains(in.nextInt())){
                sb.append('1').append(' ');
            }else
                sb.append('0').append(' ');
        }
        System.out.println(sb);
    }

}

 

---

 

최종 코드

 

위의 시간 초과가 뜨지 않으려면 이진 탐색을 사용해야한다.

기존 일반 배열을 쓰지 않고 arraylist를 사용했더니 복잡해져 일반 배열을 사용하였다.

 

 

import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        int m = in.nextInt();

        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < m; i++) {
            if(binarySearch(arr, in.nextInt()) >= 0){
                sb.append('1').append(' ');
            }else
                sb.append('0').append(' ');
        }
        System.out.println(sb);
    }

    private static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length -1;

        while (left <= right){
            int mid = (left+right)/2;

            if(key < arr[mid]){
                right = mid -1;
            }else if(key > arr[mid]){
                left = mid +1;
            }else
                return mid;
        }
        return -1;

    }

}