자바 [Algorithm] 이분탐색 - 백준 10815 숫자 카드

1. 문제

 

2. 접근법

간단한 문제이다. 4번째 카드들이 2번째 줄에 있는지 없는지 확인하는 문제!

탐색 문제이고 시간 복잡도를 계산하면 2중 반복문은 안되는 걸 알 수 있었는데 대충 풀다보니 시간 초과가 나서 실패했다.

Arrays.binarySearchd의 메서드를 사용하니 다시 풀 수 있었다~

 

Arrays.binarySearch 사용법

1. 정렬된 배열에서 특정 값을 찾기 위해 사용된다.

2. 이 함수는 배열에 해당 값이 있는 경우 그 인덱스를 반환하고, 없는 경우 음수를 반환한다.

3. 코드

package week09;

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

public class Baek10815 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

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

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

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


        Arrays.sort(arr);

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

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

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


        for (int i = 0; i < M; i++) {
            if (Arrays.binarySearch(arr, arr2[i]) >= 0) {
                result[i] = 1;
            } else {
                result[i] = 0;
            }
        }

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

 

4. 틀린 코드

처음에는 2중 반복문으로 풀었더니 시간 초과가 났다.

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if(arr2[i] == arr[j]){
                result[i] = 1;
            }
        }
    }