문제

---

배경 지식

[탐색 알고리즘 시간 복잡도]

이진 탐색 알고리즘은 Up-Down 게임과 유사하다.

---

문제 이해

1. N을 입력받는다.
2. N개의 자연수를 입력받아 배열 A에 저장한다.
3. M을 입력받는다.
4. M개의 자연수를 입력받아 배열 A에 존재하면 1을, 그렇지 않으면 0을 출력한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class FindNumber {
  static int N, M;
  static int[] A;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    A = new int[N];

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }

    Arrays.sort(A);

    st = new StringTokenizer(br.readLine());
    M = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < M; i++) {
      int result = Arrays.binarySearch(A, Integer.parseInt(st.nextToken()));

      if(result >= 0) System.out.println("1");
      else System.out.println("0");
    }
  }
}

---

코드 설명

탐색 알고리즘 중 가장 시간 복잡도가 적은 Binary Search를 이용하기 위한 조건은 탐색하고자 하는 배열이 정렬이 되어 있어야 한다.

• N을 입력받는다
• A를 입력받아 배열에 값을 넣어 준다.
• A 배열을 정렬해준다.
  Arrays.sort() 함수는 DualPivotQuickSort 방식으로 평균 O(nlog(n)), 최악 O(n2)의 시간 복잡도를 가진다
• M을 입력받는다
• 입력받은 값들이 A배열에 있는지 탐색한다.
  - 이진 탐색 알고리즘을 이용하여 값이 있으면 1, 없으면 0을 리턴한다.

  ---

결과