[PS] 99클럽 코테 스터디 13일차 TIL (숫자카드)

문제

문제 링크

풀이

binarySearch

자바 Arrays 패키지에 있는 binarySearch() 메소드를 이용해 풀었다. 해당 메소드는 정렬된 상태의 배열에서 원하는 값을 찾아주는 역할을 한다. 내부적으로 이분탐색으로 구현되어 있어 O(log n) 의 시간복잡도를 가진다.

Arrays.binarySearch() 는 값을 찾으면 해당 인덱스를 반환하고, 그렇지 않으면 -(insertion point) - 1 의 값을 반환한다. insertion point 란 배열에서 해당 값보다 큰 최초의 인덱스를 말한다. 예를들어 배열 [1, 3, 5, 7, 9] 에서 6 을 찾으려고 하면 6보다 큰 최초의 위치는 7의 위치인 3 이 된다. 여기에 -1을 곱하고 -1을 한 값인 -4를 반환한다. 즉, 찾으려는 값이 있으면 양수, 없으면 음수라는 점을 이용해 문제를 해결한다.

int[] test = {1, 3, 5, 7, 9};
Arrays.sort(test);  // 이분탐색은 정렬된 상태의 배열에서 동작한다.
int search = Arrays.binarySearch(test, 6);
System.out.println("search = " + search);    // search = -4

public class Main {

  static FastReader scan = new FastReader();
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) {
    input();
  }

  static void input() {
    int N = scan.nextInt();
    int[] arr = new int[N];
    for (int i = 0; i < N; i++) {
      arr[i] = scan.nextInt();
    }
    Arrays.sort(arr);
    int M = scan.nextInt();
    for (int i = 0; i < M; i++) {
      int isExist = Arrays.binarySearch(arr, scan.nextInt());
      sb.append(isExist >= 0 ? 1 : 0).append(" ");
    }
    System.out.println(sb);

  }

  static class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    public FastReader(String s) throws FileNotFoundException {
      br = new BufferedReader(new FileReader(new File(s)));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }
  }

}