[백준] 8983: 사냥꾼 - JAVA

in Algorithm on 정렬

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

풀이

x축에 사냥꾼들의 위치가 주어지고, 동물의 좌표가 x, y 좌표로 주어진다.

사냥꾼의 총의 사정거리가 주어지고, 동물을 몇 마리 잡을 수 있는지 구하는 문제이다.

동물을 기준으로 자신을 잡을 수 있는 사냥꾼이 있는지 판별했다.

동물의 위치로부터 사정거리 내에 있는 x축 위 점의 최소, 최대를 구한다. 이를 left, right로 하고 이분탐색을 통해 사냥꾼의 위치가 이 범위 안에 있는지 확인한다.

메모리: 55416KB

시간: 700ms

언어: Java 11

코드

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

public class Main {
    static class Animal {
        int x;
        int y;

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

    static int m, n, l;
    static int[] hunter;

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

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

        Animal[] animals = new Animal[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            animals[i] = new Animal(x, y);
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer += searchWhoCanHuntMe(animals[i]);
        }

        System.out.println(answer);
    }

    private static int searchWhoCanHuntMe(Animal animal) {
        int start = 0;
        int end = m - 1;
        int left = animal.x - (l - animal.y);
        int right = animal.x + (l - animal.y);

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

            if (hunter[mid] >= left && hunter[mid] <= right) {
                return 1;
            }

            if (hunter[mid] < left) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return 0;
    }

}