[백준] 1920번 : 수 찾기

1920번: 수 찾기

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int binarySearch(int[] arr, int a) {   //이분 탐색
        int pl = 0;
        int pr = arr.length - 1;
        while (pl <= pr) {
            int pc = (pl + pr) / 2;

            if (arr[pc] == a) {       //찾으려는 수가 중앙값에 위치해 있다면 바로 1 리턴
                return 1;
            } else if (a < arr[pc]) {  //찾으려는 수가 중앙 인덱스값보다 작을 때
                pr = pc - 1;           //마지막인덱스를 중앙 인덱스에서 1을뺀 값을 저장해준다
            } else if (a > arr[pc]) {  //찾으려는 수가 중앙 인덱스값보다 클 때
                pl = pc + 1;           //첫인덱스값이 들어간 pl을 중앙 인덱스 + 1로 저장
            }
        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int[] arr2 = new int[m];
        st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < m; i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        /*for (int i = 1; i < arr.length; i++) {       //이진검색을 위해 배열 오름차순으로 정렬
            int j;
            int tmp = arr[i];
            for (j = i; j > 0 && arr[j - 1] > tmp; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = tmp;
        }*/

        for (int i = 0; i < arr2.length; i++) {
            System.out.println(binarySearch(arr, arr2[i]));
        }
    }
}

해결 방법

• 주어진 수와 배열 값들을 입력 받고 이진 탐색을 위해 arr1을 정렬해준다.
  • 삽입 정렬은 외부 루프가 arr.length-1번 도는 동안 비교가 계속 이루어지기 때문에 최악의 경우 시간 복잡도가 O($n ^2$)이다.
    • 이로 인해 시간 초과가 발생하여 그냥 Arrays.sort() 메서드를 사용했다. ( 퀵, 병합 정렬 등을 공부해보자)
• 이진 탐색 알고리즘을 메서드로 정의하고 for문으로 arr2의 요소들을 메서드의 인자 값에 넣어준다.