[백준] 1920번 : 수 찾기 - JAVA [자바]

문제

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

---

수도코드 작성

이진탐색을 사용해서 뒤에 받아온 문자들을 앞에 배열과 비교하면 된다고 생각했다.

---

작성한 코드

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

public class test01 {
    public static void main(String[] args) {
        // 입력문
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder(); // 최대한 시간을 줄이기위해 StringBuilder사용

        int N = sc.nextInt();
        int[] A = new int[N];

        for (int i = 0; i < A.length; i++) {
            A[i] = sc.nextInt();
        }

        int M = sc.nextInt();

        Arrays.sort(A); // 이진탐색은 정렬 후에 사용해야 하므로 선정렬
        
        for (int i = 0; i < M; i++) {
            if (binarySearch(A, sc.nextInt()) >= 0) {
                sb.append(1).append("\n");
            } else sb.append(0).append("\n");
        }

        System.out.println(sb);

    }

    //이진탐색 함수
    public static int binarySearch(int[] arr, int target){
        int left = 0;
        int right = arr.length-1;

        while(left<=right){
            int mid = (left+right)/2;
            if(target == arr[mid]){
                return 0;
            }
            else if(target < arr[mid]){
                right = mid - 1;
            }
            else left = mid + 1;
        }
        return -1;
    }
}

---

보완할 점 / 헷갈린 점

처음에는 이진탐색말고 순차적 탐색으로 실행했는데 시간이 너무 차이가 나서
시간복잡도 logN인 이진탐색을 사용하기로 했다.

그래도 계속 시간초과가 떠서 보니 이진탐색 함수를 실행할 때마다 앞에 배열을 sort하고 있어서 시간초과가 나고
그리고 뒤에 숫자들을 배열로 받을려고 하니까 더 시간초과가 났다
그래서 하나씩 비교할 때 마다 입력 받는 형식으로 바꾸었고 Arrays.sort도 for문 들어가기 전에 한번만 실행하게 하니까 시간초과에서 벗어날 수 있었다.