백준 - 10815번 - 숫자 카드

10815번

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

public class Main {

	static StringBuilder sb = new StringBuilder();
	static int[] num;
	static int[] check;
	static int n, m;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(bf.readLine());
		num = new int[n];

		StringTokenizer st = new StringTokenizer(bf.readLine());
		for (int i = 0; i<n; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}

		m = Integer.parseInt(bf.readLine());
		check = new int[m];

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i<m; i++) {
			check[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(num);

		for (int i = 0; i<check.length; i++) {
			if (bs(check[i])) {
				sb.append(1+" ");
			}
			else {
				sb.append(0+" ");
			}
		}

		System.out.println(sb);
	}
	static boolean bs(int checkNum) {
		int max = num.length;
		int min = 0;
		int mid = 0;

		while (min < max) {
			mid = (max + min) / 2;

			if (checkNum == num[mid]) {
				return true;
			} else if (checkNum < num[mid]) {
				max = mid;

			} else if (checkNum > num[mid]) {
				min = mid + 1;

			}
		}
		return false;
	}
}

풀이

첫번째 주어진 N개의 숫자와 두번째 주어진 숫자 M개를 입력받고 있는지 없는지 판단하는 문제다.

있는지 없는지 확인할때 N개의 숫자를 하나하나 찾아보는것은 비효율적이다. 오름차순으로 N개 배열을 정렬하고 O(log n)의 시간복잡도를 갖도록 이분탐색을 해야한다.