[백준] 1920 수 찾기

 

이젠 피할 수 없는 알고리즘 ,,, 자료구조 ,,,

 

package sort;

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

public class Boj1920 {
    //이분 검색
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr1 = new int[n];
        for (int i = 0; i < n; i++) {
            arr1[i] = sc.nextInt();
        }
        //정렬
        Arrays.sort(arr1);
        int m = sc.nextInt();
        int[] arr2 = new int[m];
        for (int i = 0; i < m; i++) {
            arr2[i] = sc.nextInt();
        }

        //이진 검색
        StringBuilder sb = new StringBuilder();
        for (int i : arr2) {
            if(Arrays.binarySearch(arr1, i) >= 0){ //존재 여부 확인
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }

        System.out.println(sb);


    }
}

 

이진검색을 하기 전에는 정렬을 꼭 해주어야 한다.

 

Arrays.sort()로 정렬 먼저 해준 후에 (오름차순)

 

이 문제에서는 이진검색 내장 메서드를 사용했다.

 

 

binarySearch 메서드

public static int binarySearch(int[] a, int key)

 

1. 매개변수:
   • a: 검색 대상이 되는 정렬된 배열.
   • key: 찾으려는 값.
2. 반환값:
   • 양수(0 이상): key가 배열 내에 존재하는 경우, 해당 값의 인덱스를 반환.
   • 음수: key가 배열 내에 없는 경우, −(삽입점)−1)-(삽입점) - 1)−(삽입점)−1)을 반환.