99클럽 코테 스터디 17일차 TIL + LeetCode 1385 (Find the Distance Value Between Two Arrays, java)

오늘의 학습 키워드

• 이분탐색

 

문제 탐색하기

문제 풀이 설계하기

arr1[i ] - arr2[j] 의 절댓값이 주어진 d의 값보다 클 때의 arr1[i] 의 수를 카운트해서 리턴해주면 되는 문제입니다.

arr2[j]를 탐색할때 이분탐색을 통해 진행하는 것으로 문제를 풀었습니다.

 

코드

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int cnt = 0;
        for(int i=0; i<arr1.length; i++){
            if(binarySearch(arr1[i], arr2, d)) cnt++;
        }

        return cnt;
    }

    private boolean binarySearch(int first, int[] arr2, int target){
        int left = 0;
        int right = arr2.length - 1;

        while(left <= right){
            int mid = left + (right-left)/2;
            if(Math.abs(first - arr2[mid]) > target){
                if(first >= arr2[mid]){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }else{
                return false;
            }
        }

        return true;
    }
}

 

오늘의 회고

이분탐색 문제를 차차 풀어가며 익숙해져야할 것 같습니다.