[BOJ] 백준 1920 - 수 찾기

👩🏻‍💻 문제

👩🏻‍💻 정답 코드

import java.util.*;
public class Main {
    public static void main(String[] args) {
	    Scanner s = new Scanner(System.in);
            boolean ex;

	    int a = s.nextInt();
	    int[] N = new int[a];
	    for (int i=0; i<a; i++){
	        N[i] = s.nextInt();
            }    

	    int b = s.nextInt();
	    int[] M = new int[b];
	    for (int i=0; i<b; i++) {
	        ex = false;
                M[i] = s.nextInt();

                for (int j=0; j<a; j++){
                    if (N[j]==M[i]){
                        ex = true;
                        break;
                    }
                }

                if (ex) System.out.print("1 ");
                else System.out.print("0 ");
            }
    }
}

N 배열에 넣은 수를 M 배열에 넣은 수와 비교해서 N배열에 존재하면 ex를 true로 바꿔놓고 break
... 이렇게 하긴 했는데 비교 대상 늘어나면 시간초과 날 것 같아서 구글링 해봤더니 이진 탐색 이용하는 문제였다.

👩🏻‍💻 개선 코드

import java.util.*;
public class Main {
    public static void main(String[] args) {
	    Scanner s = new Scanner(System.in);

	    int a = s.nextInt();
	    int[] N = new int[a];
	    for (int i=0; i<a; i++){
	        N[i] = s.nextInt();
            }
            Arrays.sort(N);

	    int b = s.nextInt();
	    int[] M = new int[b];
	    for (int i=0; i<b; i++) {
                M[i] = s.nextInt();
                int ex = Arrays.binarySearch(N, M[i]);
                if (ex<0) System.out.print("0 ");
                else System.out.print("1 ");
            }
    }
}

Arrays 클래스에 있는 이진 탐색 메서드를 활용해봤다.
정렬이 되어 있어야 한다길래 Arrays.sort(N); 해준 후,
for문 내에서 M 배열에 입력 받을 때마다 int ex = Arrays.binarySearch(N, M[i]); 으로 ex값 업데이트 후 결과를 출력했다.

이진 탐색으로 코드를 짰더니 시간이 반으로 줄었다... 신기

---

👩🏻‍💻 Remember

Arrays.binarySearch() ➡️ 탐색에 성공하면 인덱스, 실패하면 음수를 리턴

이진 탐색 - 오름차순으로 정렬되어 있는 배열에서 특정값의 위치를 찾아내는 알고리즘

배열의 중간값과 값과 찾고자 하는 값을 비교하여 중간 값보다 작으면 좌측의 데이터들을 대상으로, 중간 값보다 크면 우측의 데이터들을 대상으로 재탐색