[Java] 백준 8983번 사냥꾼

이분탐색 문제입니다.

잡을 수 있는 동물의 수를 구하는 문제입니다.
총을 쏠 수 있는 사로와 동물의 위치, 현재 총의 사거리가 주어집니다.

아래의 식으로 해당 사로에서 해당하는 동물을 잡을 수 있는지 구했습니다.

|사로x - 동물x| + 동물y > 총의 사정거리

가능한 경우 결과를 +1

불가능한 경우
현재 사로x가 동물x보다 작은 경우 - left = mid + 1
현재 사로x가 동물x보다 큰 경우 - right = mid - 1

이분탐색으로 left가 right보다 클 때까지 반복합니다.

모든 동물에 반복하여 카운트 된 수를 출력해줍니다.

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int result = 0;
    int m = Integer.parseInt(st.nextToken());
    int n = Integer.parseInt(st.nextToken());
    int l = Integer.parseInt(st.nextToken());
    int[] arr = new int[m];
    Pair[] target = new Pair[n];

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < m; ++i) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

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

      target[i] = new Pair(y, x);
    }

    Arrays.sort(arr);

    for (int i = 0; i < n; ++i) {
      int left = 0;
      int right = m - 1;
      while (left <= right) {
        int mid = (left + right) / 2;

        if (Math.abs(arr[mid] - target[i].x) + target[i].y > l) {
          if (arr[mid] < target[i].x) {
            left = mid + 1;
          } else if (arr[mid] > target[i].x) {
            right = mid - 1;
          } else {
            break;
          }
        } else {
          ++result;
          break;
        }
      }
    }

    bw.write(result + "\n");
    bw.close();
  }

  public static class Pair {
    int y;
    int x;

    public Pair(int y, int x) {
      this.y = y;
      this.x = x;
    }
  }
}