[JAVA]수 찾기(Baekjoon)

문제

문제

 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 $-2^{31}$ 보다 크거나 같고 $2^{31}$보다 작다.

출력

 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

풀이

 이 문제를 보고 바로 이진 탐색을 떠올렸다. 그러나, 이진 탐색은 정렬된 배열에서 사용 가능하기에 정렬을 할 필요가 있었고, 정렬을 하는 알고리즘에 대해 고민을 했다.
 $nlogN$의 Time Complexity를 가지는 정렬인 Merge Sort나 Quick Sort들을 생각했고, 이를 구현할 생각을 하였다. 혹은 Heap 자료구조를 사용하여 해결을 해야하나 생각했으나 Heap은 삽입이 $nlogN$의 Time Complexity를 가지기 때문에 본 문제에는 정렬을 하여 이진 탐색을 수행하는 것이 더 효율적일거라는 생각이 들었다.
 그러나 고민을 하다 그냥 구현되어 있는 Sort함수를 사용하기로 하였다. 기본적으로 제공하는 정렬 함수가 $nlogn$의 Time Complexity를 가지기 때문이다. 그리고 따로 한번 더 정렬에 대해서 짚고 확실히 공부하고 넘어가야겠다고 다짐했다.
 이진 탐색에 대해 한번 더 짚을 포스팅을 할 것이지만 간단하게 메커니즘에 대해 요약하면,

1. 탐색 범위내의 배열의 중간 인덱스를 구한다.
2. 중간 인덱스의 값과 key값을 비교한다.
3. key값이 중간값보다 작다면 중간에서 왼쪽 부분을, 크다면 오른쪽 부분을 탐색하고 같다면 해당 인덱스를 반환하고 종료한다.

public class _1920 {
    public static int[] arr;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            if(binary_search(Integer.parseInt(st.nextToken())) >= 0)
                sb.append("1\n");
            else
                sb.append("0\n");
        }
        System.out.println(sb);
    }

    public static int binary_search(int num){
        int lo = 0;
        int hi = arr.length - 1;

        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(num < arr[mid]){
                hi = mid - 1;
            }
            else if(num > arr[mid]){
                lo = mid + 1;
            }
            else
                return mid;
        }

        return -1;
    }
}

결론

 이진 탐색의 경우에는 $logN$의 Time Complexity를 갖는다. 정렬이 선행되어야 한다는 조건이 있지만, 특정한 값을 찾을 때는 매우 효율적인 알고리즘이므로, 꼭 숙지해야할 필요가 있다!