[백준] 1920번 - 수 찾기 (Java)(○)

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

1920번: 수 찾기

 

<문제 분석>

선형탐색으로 풀면 시간초과가 발생한다.

이분탐색으로 풀어보자.

1. N개의 수를 입력받아서 오름차순으로 정렬을 해야 한다.

2. M의 수를 하나씩 이분탐색으로 찾아보자.

 

<코드 구현>

import java.util.*;
import java.io.*;

/*
[백준] 1920번 - 수 찾기 (Java)
*/

public class Main {
    static int N, M;    
    static int A[];
    static int B[];
    
    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = in.nextInt();
        }
        M = in.nextInt();
        B = new int[M];
        for (int j=0; j<M; j++) {
            B[j] = in.nextInt();
        }
    }

    int BinarySearch(int num) {
        int start = 0, end = N-1;
        while (start <= end) {
            int mid = (start + end)/2;
            if (A[mid] == num) {
                return 1;
            } else if (A[mid] < num) { // 타겟이 mid보다 커서 우측에 있을 경우
                start = mid + 1;
            } else { // 타겟이 mid보다 작아서 좌측에 있을 경우
                end = mid - 1;
            }
        }
        return 0;
        
    }
    void Solve() {
        Arrays.sort(A);
        for (int i=0; i<M; i++) {
            int ans = BinarySearch(B[i]);
            System.out.println(ans);
        }
    }

	public static void main(String[] args) {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>