[BOJ] 10815. 숫자 카드(JAVA)

📌문제

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다.
정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.
둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다.
숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다.
넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다.
이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

---

💪아이디어

1. 숫자 카드 정렬하기
   • 이분탐색을 위해 숫자 카드를 정렬한다.
   • 이 문제는 상근이가 가진 숫자카드가 숫자카드에 있는지 확인하는 문제이다.
   • 완전탐색을 할 경우 N = 1e5, M = 1e5이므로 NM = 1e10이기 때문에 시간초과가 발생할 수 있다.
   • 이분탐색을 통해 logN의 시간복잡도로 문제를 해결할 수 있다.
2. 상근이가 가진 카드보다 첫 번째 숫자카드가 크거나 마지막 숫자카드가 작으면 없는 0출력
   • 숫자카드의 첫번째는 숫자카드 중 가장 작은 수이다. 만약 상근이의 카드보다 첫 번째 카드가 크다면 숫자카드에는 상근이가 가진 숫자카드는 없는 것이다
   • 마찬가지로 숫자 카드의 마지막은 숫자 카드중 가장 큰 수 이다. 따라서 상근이 카드보다 작으면 없는 것
3. 이분탐색을 통해 상근이가 가진 카드가 있는지 확인
   • mid보다 상근이의 카드가 작으면 left를 mid+1로 이동
   • mid의 왼쪽은 무조건 상근이 카드보다 작기때문에 범위에서 제외시킨다. - mid보다 상근이의 카드가 크면 right를 mid-1로 이동
   • mid의 오른쪽은 무조건 상근이 카드보다 크기때문에 범위에서 제외시킨다.

🥂코드

import java.io.*;
import java.util.*;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int N = Integer.parseInt(br.readLine());
    int[] cards = new int[N];
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < N; i++) {
      cards[i] = Integer.parseInt(st.nextToken());
    }
    int M = Integer.parseInt(br.readLine());
    int[] sangs = new int[M];
    st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < M; i++) {
      sangs[i] = Integer.parseInt(st.nextToken());
    }
    // init
    Arrays.sort(cards);
    for (int i = 0; i < M; i++) {
      sb.append(findCards(cards, sangs[i], 0, N - 1)).append(" ");
    }
    System.out.println(sb.toString());
  } // end of class

  public static int findCards(int[] cards, int sang, int left, int right) {
    if (cards[right] < sang || cards[left] > sang) {
      return 0;
    }
    if (cards[right] == sang || cards[left] == sang) {
      return 1;
    }
    int mid = 0;
    while (left <= right) {
      mid = (left + right) / 2;
      if (cards[mid] <= sang) {
        if (cards[mid] == sang) {
          return 1;
        }
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return 0;
  }
}// end of main