[백준 1920] 수 찾기 Java 풀이

1920번: 수 찾기

 

접근

n이 최대 100,000, m이 최대 100,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[] a;

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

		// 입력 처리
		n = Integer.parseInt(br.readLine());
		a = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}

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

		m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			int x = Integer.parseInt(st.nextToken());
			int result = binarySearch(x);
			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 (a[m] == target) {
				return 1;
			} else if (a[m] > target) {
				e = m - 1;
			} else {
				s = m + 1;
			}
		}
		return 0;
	}
}