[BOJ] 8938번 | 사냥꾼 (Java)

🔗문제 보러가기

 

 

Solution

이분 탐색(Binary Search) 알고리즘으로 풀 수 있습니다. 사대 위치를 저장하는 배열을 오름차순으로 정렬한 뒤, 동물들의 위치를 순회하면서 `L` 사거리 내에 들어오는 사대를 찾으면 됩니다. 즉, 로직의 순서도는 다음과 같습니다.

 

1. 사대 위치 배열을 오름차순으로 정렬
2. 동물들의 좌표를 순회
   • 현재 동물의 `x` 좌표와 가장 가까운 사대의 좌표를 탐색 (`y` 좌표는 고정값이기에 상수로 항상 있는 수)
   • 탐색한 사대와의 거리가 `L` 이하이면 탐색 종료
     • 잡을 수 있는 동물 수 +1하고, 다음 동물 좌표로 순회
   • 탐색한 사대와의 거리가 `L`보다 크다면, 현재 동물의 x 좌표에서 사대가 왼쪽에 있는지 오른쪽에 있는지 파악
     • 사대가 왼쪽에 있다면 `left = mid + 1`
     • 사대가 오른쪽에 있다면 `right = mid - 1`

 

Source Code

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

public class BOJ8983 {
    private static int M, N, L;
    private static long[] ShootingPositions;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
        String[] inputs = br.readLine().split(" ");

        M = Integer.parseInt(inputs[0]);
        N = Integer.parseInt(inputs[1]);
        L = Integer.parseInt(inputs[2]);

        inputs = br.readLine().split(" ");
        ShootingPositions = new long[M];

        for (int i = 0; i < M; i++) {
            ShootingPositions[i] = Long.parseLong(inputs[i]);
        }

        Arrays.sort(ShootingPositions);
        int answer = 0;

        for (int i = 0; i < N; i++) {
            inputs = br.readLine().split(" ");
            long x = Long.parseLong(inputs[0]), y = Long.parseLong(inputs[1]);

            answer += binarySearch(0, M - 1, x, y);
        }

        System.out.println(answer);
        br.close();
    }

    public static int binarySearch(int left, int right, long animalX, long animalY) {
        boolean canHunt = false;

        while (left <= right) {
            int mid = (left + right) / 2;
            long turretX = ShootingPositions[mid];
            long distance = Math.abs(turretX - animalX) + animalY;

            // 사냥 가능한 거리이면 이분 탐색 중단
            if (distance <= L) {
                canHunt = true;
                break;
            }

            if (turretX < animalX) left = mid + 1;
            else                   right = mid - 1;
        }

        return canHunt ? 1 : 0;
    }
}