[BAEKJOON] 1920번 수 찾기

---

주어진 A 배열과 입력되는 수간의 비교 연산으로 포함 여부를 판단하는 문제이다.

물론, 반복문으로 배열 전체와 입력되는 수를 하나씩 비교하며 포함되는지 여부를 알 수 있다.

하지만 반복문을 사용할 경우 메모리 초과를 경험할 수 있을 것이다.

결론부터 말하자면 A 배열을 오름차순 정렬하여 이진 탐색 방법으로 타켓 수와의 비교 연산을 줄여 효율을 높인다.

위의 그림과 같이 시작과 끝 인덱스를 기준으로 mid에 해당하는 중간 지점 인덱스를 구한다.

'시작~중간' 과 '중간~끝' 중에 target이 되는 수가 어디 지점에 있는지만 알면 된다.

target이 배열의 중간을 기준으로 오른쪽과 왼쪽 부분으로 나누었을 때 어느 지점에 있는지 찾아가는 과정을 반복하면 결국 중간지점은 언제나 마지막 하나가 남을 때까지 반복할 것이고, target과 같은 수에 해당하는 인덱스 지점을 찾게 될 것이다.

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

public class Main {
	static int n, m, A[];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		A = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++)
			A[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(A);
		m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<m; i++)
			System.out.println(binary(0,A.length-1,Integer.parseInt(st.nextToken())));
	}
	private static int binary(int start, int end, int target) {
		if(start > end) return 0;
		int mid = (start+end)/2;
		if(A[mid]==target) return 1;
		if(A[mid]<target) return binary(mid+1, end, target);
		else return binary(start, mid-1, target);
	}
}

[출처]

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

1920번: 수 찾기