[백준 1920] 수찾기 - Java

 

문제링크 : https://www.acmicpc.net/problem/1920

 

1920번: 수 찾기

 

 

 

내 마음대로 풀이

 

처음에는 순차탐색을 통해서 답을 구했다.

timeout이 걸릴줄 알았는데, 어째 통과는 했다.

하지만 이 문제 풀이의 핵심은 Binary search를 활용해서 O(logn)시간에 원하는 값을 찾는 것이다.

그래서 아래와 같이

sort함수를 통해 array를 정렬한 후

Recursive Binary search 함수를 작성하여 문제를 해결했다.

 

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    static int [] A ;
    
    public static int bs(int start, int end, int input)
    {
        int mid = (start + end )/2;
        
        if (mid >= end)
            return 0;
            
        if(A[mid] == input)
        {
            return 1;
        }else if (A[mid] < input)
        {
            return bs(mid+1, end, input);
        }else {
            return bs(start, mid, input);
        }
    }
    
     public static void main(String []args){
         
        Scanner sc = new Scanner(System.in);
        
        int input = sc.nextInt();
        A = new int [input];
        for (int i = 0 ; i < input ; i++)
        {
            A[i] = sc.nextInt();
        }
        
        int input2 = sc.nextInt();
        int check ;
        boolean exist = false;
        
        Arrays.sort(A);
        
        for (int i = 0 ; i < input2 ; i++)
        {
            check = sc.nextInt();
            System.out.println(bs(0,A.length, check));
        }
     }
}