[백준 1920] 수 찾기_자바Java

1. 문제

https://www.acmicpc.net/problem/1920

2. 풀이

재귀를 이용한 Binary Search로 문제를 해결했다.
문제에서 N의 범위는 (1 ≤ N ≤ 100,000), M의 범위는 (1 ≤ M ≤ 100,000)로 나타냈기 때문에 brute force로 풀면 O(N^2)이라 시간초과가 난다.

Binary Search(이진탐색, 이분탐색)

• 사전조건: 배열이 정렬되어 있어야한다.

1. N 크기의 arr[] 배열이 있다고 가정한다.
2. index의 최대 범위를 지정한다. 0 ~ N-1이므로 left 값은 0, right 값은 N-1
   • 코드에서는 left가 start, right가 end로 쓰인다.
3. left와 right의 중간값인 mid를 구한다. - (left + right) / 2
4. 찾고자 하는 값과 arr[mid] 값이 같은지 비교하고 범위를 조정한다.
   4-1. 같으면 return mid;
   4-2. 찾고자 하는 값이 arr[mid]보다 작으면 범위를 왼쪽 범위로 옮겨준다.
   => right = mid - 1;
   4-3. 찾고자 하는 값이 arr[mid]보다 크면 범위를 오른쪽으로 옮겨준다.
   => left = mid + 1;
5. 조정된 범위로 다시 search 함수를 호출한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static int[] NList;
	public static StringBuilder sb;
	public static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();

		// Setting about N
		int N = Integer.parseInt(in.readLine());
		NList = new int[N];
		st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < N; i++) {
			NList[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(NList);

		// Setting about M
		int M = Integer.parseInt(in.readLine());
		st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < M; i++) {
			int result = search(Integer.parseInt(st.nextToken()), 0, N - 1);
			sb.append(result == -1 ? 0 : 1).append("\n");
		}

		out.write(sb.toString());
		out.close();
		in.close();
	}

	private static int search(int num, int start, int end) {
		int mid;

		while (start <= end) {
			mid = (start + end) / 2;

			if (num == NList[mid]) {
				return mid;
			} else if (num < NList[mid]) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}

		return -1;
	}

}