[백준 2776] 암기왕 Java 풀이

2776번: 암기왕

 

접근

n이 최대 1,000,000, m이 최대 1,000,000이므로 선형 탐색을 사용한다면 최악의 경우 시간 복잡도가 O( n * m )가 될 것으로 예상됩니다. 따라서 이진 탐색을 활용하여 시간 복잡도를 O(m * logn)으로 줄일 수 있는 방법을 선택했습니다. 

 

코드

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

public class Main {
	static int n, m;
	static int[] arr;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		// 입력 처리
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());
			arr = new int[n];

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

			// 배열 arr를 오름차순으로 정렬한다.
			Arrays.sort(arr);

			m = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < m; i++) {
				int target = Integer.parseInt(st.nextToken());
				int result = binarySearch(target);
				sb.append(result).append("\n");
			}
		}

		// 결과 출력
		System.out.println(sb);
	}

	static int binarySearch(int target) {
		int s = 0;
		int e = n - 1;
		while (s <= e) {
			int m = (s + e) / 2;
			if (arr[m] == target) {
				return 1;
			} else if (arr[m] < target) {
				s = m + 1;
			} else {
				e = m - 1;
			}
		}
		return 0;
	}
}