백준 4158번
https://www.acmicpc.net/problem/4158
이분 탐색 문제이다.
마지막에 0 0이 나오는 걸 잊으면 안 된다.
이분 탐색을 통해서 같은 값이 있는지 찾으면 되는 문제이다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static int[] nArr;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (; ; ) {
String temp = br.readLine();
if (temp.equals("0 0")) break;
input(temp);
bw.write(solve());
}
bw.close();
} // End of main()
private static String solve() throws IOException {
StringBuilder sb = new StringBuilder();
int ans = 0;
for (int i = 0; i < M; i++) {
int target = Integer.parseInt(br.readLine());
int ret = binarySearch(0, N - 1, target);
if (ret != -1) ans++;
}
sb.append(ans).append('\n');
return sb.toString();
} // End of solve()
private static int binarySearch(int low, int high, int target) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (nArr[mid] == target) return mid;
else if (nArr[mid] > target) {
return binarySearch(low, mid - 1, target);
} else {
return binarySearch(mid + 1, high, target);
}
} // End of binarySearch()
private static void input(String temp) throws IOException {
StringTokenizer st = new StringTokenizer(temp);
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
nArr = new int[N];
for (int i = 0; i < N; i++) {
nArr[i] = Integer.parseInt(br.readLine());
}
} // End of input()
} // End of Main class