[BOJ] 8983. 사냥꾼

lowerBound와 upperBound를 활용하여 풀 수있는 문제였다.

총의 사정거리 L에대해 사대의 위치 와 동물의 위치 x,y에 대해 다음과 같은 공식이 문제에 주어져있다.
| 사대 - x | + y <= L 
이 공식을 사대를 기준으로 다시정리해보았다.

| 사대 - x | + y <= L
| 사대 - x | <= L - y
- L + y <= 사대 - x <= L - y
- L + x + y <= 사대 <= L +x - y

이렇게 된다면 x,y 위치의 동물은 사정거리가 L 일때 - L + x + y 부터 L + x - y 사이의 사냥꾼이 한명이라도 존재하게 된다면 잡히게 되는 상황이 오게된다. 다만 L의 범위가 최대 1000000000이게 되므로 사대에 사냥꾼이 존재하는지를 확인하는 과정에서 일반적으로 접근했을때 시간초과가 발생할 수 있다. 따라서 이 과정에서 lowerBound와 upperBound를 활용해보았다. 

lowerBound는 arr에서 주어진 값과 같거나 큰 값이 나오는 첫번째 위치의 인덱스를 리턴해주고, upperBound는 arr에서 주어진 값보다 큰 값이 나오는 첫번째 위치의 인덱스를 리턴해주게 된다. 따라서 upperBound(L + x - y)의 값에서 lowerBound(- L + x + y)의 값을 빼주면 - L + x + y에서 L + x - y사이의 존재하는 사냥꾼의 수를 구할 수 있다. 

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_8983_사냥꾼 {
    static int N, M, L;
    static int[] shotArea;
    static int answer;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
 
        shotArea = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            shotArea[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(shotArea);
 
        answer = 0;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            if (y > L) {
                continue;
            }
            check(x, y);
        }
 
        System.out.println(answer);
    }
 
    static void check(int x, int y) {
        int minX = -L + y + x;
        int maxX = L - y + x;
 
        if (upperBound(maxX) - lowerBound(minX) > 0) {
            answer += 1;
        }
    }
 
    static int lowerBound(int value) {
        int startIndex = 0;
        int endIndex = N;
 
        while (startIndex < endIndex) {
            int midIndex = (startIndex + endIndex) / 2;
 
            if (shotArea[midIndex] < value) {
                startIndex = midIndex + 1;
            } else {
                endIndex = midIndex;
            }
        }
 
        return endIndex;
    }
 
    static int upperBound(int value) {
        int startIndex = 0;
        int endIndex = N;
 
        while (startIndex < endIndex) {
            int midIndex = (startIndex + endIndex) / 2;
 
            if (shotArea[midIndex] <= value) {
                startIndex = midIndex + 1;
            } else {
                endIndex = midIndex;
            }
        }
 
        return endIndex;
    }
 
}
 

 

위의 방법에선 lowerBound와 upperBound를 이용해 - L + x + y에서 L + x - y사이의 존재하는 사냥꾼의 수를 구하였지만 간단하게 이분탐색으로 아래 코드와 같은 방법으로 - L + x + y에서 L + x - y사이의 존재하는 사냥꾼의 수를 구할 수도 있다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_8993_사냥꾼_2 {
    static int M, N, L;
    static int[] shotArea;
    static int answer;
 
    public static void main(String[] args) throws Exception {
        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());
 
        shotArea = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            shotArea[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(shotArea);
 
        answer = 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());
 
            if (y > L) {
                continue;
            }
 
            int minX = -L + x + y;
            int maxX = L + x - y;
            binarySearch(minX, maxX);
        }
 
        System.out.println(answer);
    }
 
    static void binarySearch(int minX, int maxX) {
        int leftIndex = 0;
        int rightIndex = M - 1;
 
        while (leftIndex <= rightIndex) {
            int midIndex = (leftIndex + rightIndex) / 2;
 
            if (minX <= shotArea[midIndex] && shotArea[midIndex] <= maxX) {
                answer += 1;
                break;
            }
 
            if (shotArea[midIndex] < minX) {
                leftIndex = midIndex + 1;
            } else if (maxX < shotArea[midIndex]) {
                rightIndex = midIndex - 1;
            }
        }
    }
}