[그리디,이진 탐색] 백준-8983 사냥꾼 골드4 (Java)

백준-8983 : 사냥꾼

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

8983번: 사냥꾼

 

아이디어

• 모든 동물들을 X축이 가장 가까운 사대를 확인하며 사냥 가능한 동물한 수를 파악한다.

 

풀의

• 사대를 입력 받고 2분 탐색을 위해 정렬을 진행한다.
• 가장 가까운 사대를 찾고 사냥 가능한 거리 안에 있으면 사냥 가능 동물을 증가 시킨다.

코드 (java)

package Greedy.Baejoon8983;

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

public class Baejoon8983 {
    public static void main(String[] args) throws IOException {

        int result = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] MNL = br.readLine().split(" ");
        int m = Integer.parseInt(MNL[0]);
        int n = Integer.parseInt(MNL[1]);
        int l = Integer.parseInt(MNL[2]);

        int[] shotList = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(shotList);

        String[] animalInfo;
        for (int i = 0; i < n; i++) {
            animalInfo = br.readLine().split(" ");
            int absNum = searchApproxIdxAbs(shotList, Integer.parseInt(animalInfo[0]));
            if (l >= absNum + Integer.parseInt(animalInfo[1])) {
                result += 1;
            }

        }

        System.out.println(result);


    }

    // 가장 근사한 사로 찾는 함수
    public static int searchApproxIdxAbs(int[] numList, int target) {

        int start = 0;
        int end = numList.length - 1;


        while (start <= end) {
            int mid = (start + end) / 2;
            // 찾은 경우 중간점 인덱스 반환
            if (numList[mid] == target) {
                // return mid;
                return 0;
            } else if (numList[mid] > target) end = mid - 1;
            else start = mid + 1;
        }


        if (start < 0) start = 0;
        if (end < 0) end = 0;
        if (start >= numList.length) start = numList.length - 1;
        if (end >= numList.length) end = numList.length - 1;

        return Math.abs(numList[start] - target) > Math.abs(numList[end] - target) ? Math.abs(numList[end] - target) : Math.abs(numList[start] - target);
        // return Math.abs(numList[start] - target) > Math.abs(numList[end] - target) ? end : start;

    }

}