수 찾기 - 1920

문제

풀이

import java.util.*;

// 수 찾기 - S4 - 정렬
public class ex1920 {

    public static int binarySearch(int[] arr , int key){
        int lt=0;
        int rt=arr.length-1;

        while(lt<=rt){
            int mid = (lt+rt)/2;

            if(key<arr[mid]) rt = mid-1;     
            else if(key>arr[mid]) lt = mid+1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

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

        // 배열은 반드시 정렬되어있어야한다. -> 이분탐색 필수조건
        Arrays.sort(arr);

        int m = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<m; i++) {
            int key = sc.nextInt();
            // 찾고자 하는 값이 있을 경우 1, 없을 경우 0을 출력해야한다.
            if(binarySearch(arr,key) >= 0) {
                sb.append(1).append('\n');
            }
            else {
                sb.append(0).append('\n');
            }
        }
        System.out.println(sb);
    }
}

이 문제는 2중 for문 , ArrayList의 contains() 등등 일반적인 방식으로 풀면 전부 다 시간초과가 발생한다. 이럴 때 원하는 값을 찾고자 할때 그 값이 배열안에 있는 지 없는 지 효율 좋게 찾는 방법은 이분탐색이다. 일반적인 탐색 알고리즘 중에서 가장 효율이 좋다.

이분탐색의 필수조건이 있는데 그것은 배열이 항상 정렬되어있어야한다.

binarySearch()를 만들어 mid값을 구하고 반씩 쪼개가면서 lt,rt를 수정해간다. 그렇게 값을 찾아서 있으면 mid값을 리턴하고 없으면 -1을 리턴한다.
sb에 담아서 출력해주면 된다.