[JAVA] 백준 (골드4) 8983번 사냥꾼

링크

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

---

입력 예제

4 8 4
6 1 4 9
7 2
3 3
4 5
5 1
2 2
1 4
8 4
9 4

---

출력 예제

6

---

풀이

각 사대들로 부터 거리가 사정거리 내외인 동물의 수를 구해야 한다. 이때 사대와 동물의 수는 최대 100,000개이므로, 완전 탐색을 한다면 $O(n^2)$으로 매우 비효율적인 연산이 된다. 따라서 사대의 위치를 정렬한 후, 각 동물의 x좌표에 대해 이진 탐색을 하여 가장 가까운 사대를 찾는다. 이렇게 하면 시간 복잡도는 $O(Nlog_2M)$이 된다.

사대와 동물의 거리는 x좌표의 차이의 절댓값에 y좌표를 더한 값이 된다. 결국 x좌표의 차이가 사정 거리 내인지 여부를 결정하므로 x좌표 차이에 따라 이진 탐색을 진행한다.

전체 코드

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

/*
백준 / 사냥꾼 / 골드4
https://www.acmicpc.net/problem/8983
 */
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());  //사대의 수
        int N = Integer.parseInt(st.nextToken());  //동물의 수
        int L = Integer.parseInt(st.nextToken());  //사정거리

        int[] sadae = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            sadae[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sadae);  //이진 탐색을 위해 정렬

        int result = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            //(x, y)에서 가장 가까운 사대를 탐색
            int s = 0;
            int e = M - 1;
            boolean isCaught = false;

            while (s <= e) {
                int m = (s + e) / 2;
                int d = Math.abs(sadae[m] - x) + y;
                if (d <= L) {
                    isCaught = true;
                    break;
                }

                if (sadae[m] < x) {  //사대가 왼쪽에 있을 때
                    s = m + 1;
                } else if (sadae[m] >= x) {  //사대가 오른쪽에 있을 때
                    e = m - 1;
                }
            }

            if (isCaught) {
                result++;
            }
        }

        System.out.println(result);
    }
}