알고리즘
[백준 1920] 수 찾기 Java 풀이
빠르게 핵심만
2024. 4. 18. 17:29
접근
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;
}
}