[백준 8983번] 사냥꾼 (java)

8983번: 사냥꾼

 

이 문제는 이분탐색을 이용하여 해결할 수 있다.

 

사대의 위치를 arr 배열에 오름차순으로 정렬한다.

정렬 전 : 6 1 4 9

정렬 후 : 1 4 6 9

 

특정 동물의 위치에서 가장 가까운 사대의 위치를 이분탐색으로 찾는다.

이분탐색을 진행하는 방법은 다음과 같다.

 

arr[middle] == x

이분탐색 범위(left ~ right)에서 arr[middle]가 동물의 x좌표와 일치한다면, 즉 사대가 같은 세로 일직선 상에 존재한다면 이 때의 사대가 동물과의 거리가 가장 짧으므로 middle 위치를 반환한다.

 

arr[middle] < x

이분탐색 범위(left ~ right)에서  arr[middle]가 동물의 x좌표보다 작다면,

left = middle + 1로 변경한다. 사대가 동물의 왼쪽에 있을 때는 오른쪽에 있는 사대일수록 동물간의 거리가 좁아지기 때문이다.

 

 

arr[middle] > x

이분탐색 범위(left ~ right)에서 arr[middle]가 동물의 x좌표보다 크다면,

right = middle -1로 변경한다. 사대가 동물의 오른쪽에 있을 때는 왼쪽에 있는 사대일수록 동물간의 거리가 좁아지기 때문이다.

 

 

이렇게 이분탐색으로 특정 동물과 가장 가까운 위치에 있는 사대를 구한 후,

해당 사대와 동물간의 거리가 L보다 작거나 같다면 그 동물은 사냥을 당하기 때문에 count를 증가시킨다.

 

동물의 수인 N만큼 반복했을 때 최종 count가 사냥을 할 수 있는 동물의 수가 된다.

 

 

소스코드 : 

	import java.io.*;
	import java.util.Arrays;
	public class n08983 {
	static int M, N, L;
	static int[] arr;
	static int cnt;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] sarr = br.readLine().split(" ");
	M = Integer.parseInt(sarr[0]);
	N = Integer.parseInt(sarr[1]);
	L = Integer.parseInt(sarr[2]);
	arr = new int[M];
	sarr = br.readLine().split(" ");
	for (int i = 0; i < M; i++)
	arr[i] = Integer.parseInt(sarr[i]);
	Arrays.sort(arr);
	for (int i = 0; i < N; i++) {
	sarr = br.readLine().split(" ");
	int x = Integer.parseInt(sarr[0]);
	int y = Integer.parseInt(sarr[1]);
	int pos = binSearch(x, y, 0, M - 1);
	int dist = Math.abs(arr[pos] - x) + y;
	if (dist <= L)
	cnt++;
	}
	bw.write(cnt + " ");
	bw.flush();
	}
	public static int binSearch(int x, int y, int left, int right) {
	int pl = left;
	int pr = right;
	do {
	int pc = (pl + pr) / 2;
	int dist = Math.abs(arr[pc] - x) + y;
	if (dist <= L || arr[pc] == x)
	return pc;
	if (arr[pc] < x)
	pl = pc + 1;
	else
	pr = pc - 1;
	} while (pl <= pr);
	if (pl > right)
	return pr;
	if (pr < left)
	return pl;
	return (Math.abs(arr[pl] - x) < Math.abs(arr[pr] - x) ? pl : pr);
	}
	}

view raw 8983.java hosted with ❤ by GitHub