백준_8983_사냥꾼

풀이

입력값이 순서대로 정렬되어있지 않으므로 입력을 받고 정렬을 해줍니다.
사대 같은 경우에는 오름차순으로 동물 같은 경우에는 x 축이 작은 순으로 정렬해줍니다. 입력값이 크기 때문에 순차적으로 검사하기 위함이다. 만약 정렬하지 않고 모든 경우에 수를 검사한다면 시간 초과가 빵...!

저는 동물을 기준으로 순회하면서 각동물이 사대에 범위에 포함되어 잡힐 수 있는지 판단했습니다.

문제를 그림으로 표현하면 다음과 같고 대략 3가지 경우를 생각해줘야합니다.

 

첫 번째는 사대의 범위를 Y 축 기준으로 넘는 경우입니다. 이때는 어느 사대도 저위에 동물을 잡을 수 없기 때문에 다음 동물을 검사합니다.

 

두 번째는 범위에 포함되는 경우입니다. 범위에 포함되는 경우에는 현재 확인 중인 사대를 유지하면서 다음 동물로 넘어갑니다.

 

세 번째는 범위에 포함되지 않았을 때입니다. 이경우는 또 두 가지 경우로 나눠지게 됩니다. 범위에 포함되지 않았는데 만약에 동물의 X 축이 현재 확인 중인 사대에 x 축보다 작은 경우에는 절대로 다음 사대에 포함될 수 없습니다 그렇기

때문에 얼른 다음 동물을 검사하러 넘어갑시다. 만약에 반대로 동물의 X 축이 현재 확인 중인 사대에 X 보다 크다면 다음 사대에 포함될 가능성이 존재하기 때문에 다음 사대를 검사해 줍니다.

 

물론 추가적으로 확인해줘야 하는 사항도 존재합니다. 만약 현재 검사하고 있는 동물이 마지막 사대의 범위를 넘어간다면 더 이상 로직을 수행하지 않고 종료하면 됩니다. 동물을 X 축 기준으로 정렬했기 때문에 그다음 동물들은 절대로 잡히지 않기 때문이죠

 

다음은 전체 코드입니다. 입력 부분을 제외하면 생각보다 로직이 간단합니다.

public class 사냥꾼 {

    static int M, N, L; // 사대의수, 동물의수, 사정거리
    static int gunLocation[];
    static int animalLocation[][];
    static int catchedAnimalCount = 0;
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        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());



        gunLocation = new int[M];
        animalLocation = new int[N][2];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < M; i++) {
            gunLocation[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(gunLocation);

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            animalLocation[i][1] = Integer.parseInt(st.nextToken());
            animalLocation[i][0] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(animalLocation, (a, b)->{
            if(a[1] == b[1]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });



        int gunIndex= 0;

        for(int i = 0; i < animalLocation.length; i++) {
            if(animalLocation[i][0] > L ) continue;
            if(animalLocation[i][1] > gunLocation[M - 1] + L) break;

            for(int j = gunIndex; j < M; j++) {
                int distance = Math.abs(gunLocation[j] - animalLocation[i][1]) + animalLocation[i][0];

                if(distance <= L) {
                    gunIndex = j;
                    catchedAnimalCount++;
                    break;
                }
                if(animalLocation[i][1] < gunLocation[j]) break;
            }


        }

        System.out.println(catchedAnimalCount);

    }
}