[99클럽 코테스터디 TIL 23일차] LeetCode 1385. Find the Distance Value Between Two Arrays 해설 및 풀이 (Java)

LeetCode 1385. Find the Distance Value Between Two Arrays 

https://leetcode.com/problems/find-the-distance-value-between-two-arrays/description/

 

---

 

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.

The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

 

Example 1:

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2

Explanation: 
For arr1[0]=4 we have: 
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
For arr1[1]=5 we have: 
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2

 

Example 2:

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2

 

Example 3:

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1
 

Constraints:

1 <= arr1.length, arr2.length <= 500
-1000 <= arr1[i], arr2[j] <= 1000
0 <= d <= 100

---

문제 유형

Array Two Pointers Binary Search Sorting

 

풀이 방법 도출

 

주어진 두 정수 배열 arr1, arr2와 정수 d가 있을 때, arr1[i]의 원소 중에서 arr2[j]의 어떤 값과도 거리 차가 d 이하인 값이 존재하지 않는 경우의 개수를 구하는 문제입니다.

 

1. arr2를 정렬하여 이진 탐색이 가능하도록 준비합니다.
2. arr1의 각 원소를 순회하면서, arr2 안에 해당 원소와의 거리 차가 d 이하인 값이 있는지를 이진 탐색을 통해 확인합니다.
3. 해당 조건을 만족하는 값이 없다면 해당 원소는 유효하므로 결과 카운트를 증가시킵니다.
4. 이 과정을 반복한 뒤, 최종 카운트를 반환합니다.

시간 복잡도

• 정렬: O(M log M)
• 이진 탐색: O(N log M)

---

핵심 코드 삽입 및 설명

import java.util.Arrays;

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2); // 이진 탐색을 위해 arr2 정렬
        int count = 0;

        for (int num : arr1) {
            if (isDistanceValue(num, arr2, d)) {
                count++; // 조건을 만족하면 count 증가
            }
        }

        return count;
    }

    // num과 arr2의 원소 사이에 거리가 d 이하인 값이 있으면 false
    private boolean isDistanceValue(int num, int[] arr, int d) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 거리 조건에 맞지 않으면 false
            if (Math.abs(num - arr[mid]) <= d) {
                return false;
            }
            // arr[mid]가 num보다 너무 작으면 오른쪽 탐색
            else if (arr[mid] < num - d) {
                left = mid + 1;
            }
            // arr[mid]가 num보다 너무 크면 왼쪽 탐색
            else {
                right = mid - 1;
            }
        }

        return true; // 모든 값과의 거리가 d보다 큼
    }
}