백준 1920 자바(이분탐색)

String의 contains메서드를 사용하면 되지 않을까?생각하고 코드를 짰다.

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

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

     br.readLine(); // 사용되지 않음. 
     String str = br.readLine();
     int second_N = Integer.parseInt(br.readLine());
     int[] arr = new int[second_N];
     String str2 = br.readLine();
     StringTokenizer st = new StringTokenizer(str2," ");
     String[] ch = new String[str2.length()];
     for(int i=0;i<second_N;i++){
        ch[i] = st.nextToken();
     } 
     for(int i=0;i<second_N;i++){
      if(str.contains(ch[i])) arr[i] = 1;  
      System.out.println(arr[i]);
     }
    }
}

코드를 돌려보면 문제에서 의도한대로 작동하기는 한다.하지만 제출하면 시간초과가 뜬다...contains 메서드가 성능이 떨어져서 그런거 같다.

그래서 좀 찾아봤고 이 문제는 이진검색 문제였다.옛날에 책에서 본 내용인데,이를 코드로 구현하는건 처음이다.내림차순으로 정렬되어 있는 배열을 반으로 쪼갠뒤 비교하고 또 다시 반으로 쪼갠뒤 비교하는 알고리즘을 사용해야 한다.

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

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

     int first_N = sc.nextInt();
     sc.nextLine();
     int[] arr = new int[first_N];
     // 검사 대상이 되는 배열
     for(int i=0;i<first_N;i++){
        arr[i] = sc.nextInt();
     }
     Arrays.sort(arr);
     int second_N = sc.nextInt();
     sc.nextLine();
     int[] arr2 = new int[second_N];
     //검사할 배열
     for(int i=0;i<second_N;i++){
        arr2[i] = sc.nextInt();
     }
     //정답지 배열
     int[] sol_arr = new int[second_N];

     for(int i=0;i<second_N;i++){
        // 검사 대상이 되는 배열과 검사할 숫자를 집어넣는다.
        sol_arr[i] = binarySearch(arr,arr2[i]);
        System.out.println(sol_arr[i]);
     }
    }

    public static int binarySearch(int[] arr,int key){
        int first = 0;
        int last = arr.length-1;
		// 이 부분 코드가 중요!
        while(last>=first){
            int mid = (first+last)/2;
            if(arr[mid]<key){
                first = mid+1;
            }else if(arr[mid]>key){
                last = mid-1;
            }else{
                return 1;
            }
        }
        return 0;
    }

}

자바에서는 Arrays.binarySearch() 클래스를 제공한다.

Arrays.binarySearch(arr,arr2[i]);대충 이렇게 사용하면 된다.

arr2[i] 값에 해당하는 인덱스를 반환한다.반환값을 바꿀수 없기에 이 문제에 적합하지는 않다.