[LeetCode] 1385. Find the Distance Value Between Two Arrays

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

Find the Distance Value Between Two Arrays - LeetCode

Find the Distance Value Between Two Arrays - Easy

 

arr1과 arr2와 d가 주어졌을때,

arr1에서 꺼낸 수를 a1, arr2에서 꺼낸 수를 a2라고 할때,

모든 a2에 대해 | a2 - a1 | > d 를 만족하는 a1의 개수를 구하는 문제다.

 

저 범위를 만족하는 a2는 a1+d 보다 크거나 a1-d보다 작아야 한다.

arr1을 훑으며, 그때마다 binary search로 arr2에서 a1-d와 a1+d를 찾아준다.

각각의 결과를 l,r이라고 하자.

 

binary search는 원하는 결과가 없을 경우, 가장 가까운 값을 뽑기 때문에

arr2[l]이 a1-d 보다 작을수도, 같을수도, 클수도 있다.

만약 작을 경우엔 한칸만 오른쪽으로 가면 a1-d보다 큰수가 되고,

클 경우엔 한칸만 왼쪽으로 가면 a1-d보다 작은 수가 된다.

이를 이용해, arr2[l]이 a1-d보다 크거나 같을 경우엔 l--를,

반대로 r에서는 a1+d보다 작거나 같을땐 r++을 해주자.

 

그러면 위의 식을 만족하는 범위는 0~l , r~arr2.size()-1 이 될 것이다.

l과 r이 이어져 있다면 즉, r-l = 1 이라면 모든 범위에서 저 식을 만족하므로 결과에 ++을 해주자.

 

전체 풀이 코드

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int ret = 0;
        sort(arr2.begin(), arr2.end());
        for (int n:arr1) {
            int r = bs(arr2,n+d);
            int l = bs(arr2,n-d);
            if (arr2[l]>=n-d) l--;
            if (arr2[r]<=n+d) r++;
            ret += r-l==1?1:0;
        }
        return ret;
    }
    int bs(vector<int>& vec, int n) {
        int l=0, r=vec.size()-1, mid = (l+r)/2;
        while (l<r) {
            if (vec[mid]<n) l=mid+1;
            else if (vec[mid]>n) r=mid-1;
            else return mid;
            mid = (l+r)/2;
        }
        return l;
    }
};