이진탐색- 코딩테스트 JAVA

Find the Distance Value Between Two Arrays

 

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

 

 

---

 

 

<전체 코드1>

1. 부루트포스 방식 

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
    	int count = 0;
        for(int a : arr1){
        	boolean isValid = true;
        	for(int b : arr2){
            	if(Math.abs(a-b) <= d){
                	isValid = false;
                    break;
                }
            }
            if(isValid){
            	count++;
            }
       }
       return count;
   }
}

 

 

흠냐 너무 어렵게 생각함.

arr1 순회하고 그 안에서 arr2 순회하면서 배열 내부 정수들 비교하면 된다.

 

브루트포스 방식은 쉽게 말하면 가능한 모든 경우를 전부 다 시도해서 값을 찾는 방식이다. 

 

 

**중요

 

Math.abs(a-b)

- a와 b 사이의 절댓값 거리를 의미함.

 

- Math.abs(-5) = 5 

이런 식으로 절댓값을 붙여서 값을 리턴함.

 

위의 문제에서는 거리를 물어봤기 때문에 Math.abs(a-b)를 사용해서 구하면 된다!

 

 

 

 

<전체 코드2>

2. 이진 탐색 방식

import java.util.Arrays;

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

        for (int a : arr1) {
            if (!hasCloseElement(arr2, a, d)) {
                count++;
            }
        }

        return count;
    }

    // arr2에서 a와 |a - arr2[j]| <= d인 원소가 있는지 이진 탐색으로 확인
    private boolean hasCloseElement(int[] arr2, int a, int d) {
        int left = 0, right = arr2.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int diff = Math.abs(arr2[mid] - a);

            if (diff <= d) return true;
            if (arr2[mid] < a) left = mid + 1;
            else right = mid - 1;
        }

        return false;
    }
}

 

1) Arrays.sort(arr2); 

- 우선 이진 탐색을 위해 정렬을 하고,

 

2) for (int a : arr1) {
    if (!hasCloseElement(arr2, a, d)) {
        count++;
    }
}

- arr1 의 원소를 하나 꺼내서 함수로 ㄱㄱ

 

 

 

[ 이진 탐색 과정 ]

3) int left = 0, right = arr2.length - 1;

- 왜 right 가 arr2.length-1 인가? 

> 처음에는 양 끝 인덱스로 시작하는데, 인덱스는 0부터 시작하므로 길이 -1을 해야 끝 인덱스임.

 

 

4)

while (left <= right) {
    int mid = left + (right - left) / 2;
    int diff = Math.abs(arr2[mid] - a);

 

- 왜 int mid = left + (right - left) / 2; 이렇게 하지?

 

**중요

 

만약 left = 2_000_000_000; 
        right = 2_000_000_010; 일 때

 

left+right는  4_000_000_010이 돼서 int 범위를 넘을 수도 있음.

 

근데, right - left는 차이값이기 때무에 절대 크지 않음. 

-> 무슨 말이냐면, 배열이 아주 크더라고 각 반복마다 절반씩 범위를 줄여가기 때문에 right-left는 바르게 줄어든다. 

 

!! 즉, 정수 오버플로우 위험

을 방지하기 위해서  i nt mid = left + (right - left) / 2 이렇게 함.

 

 

4.1)

int diff = Math.abs(arr2[mid] - a);

 

- arr2[mid]와 a를 비교하는 이유는 둘이 얼마나 가까운지 확인하기 위함임.

- 즉, arr2가 정렬되어 있기 때문에 이진 탐색을 사용해서 arr2의 중간값부터 빠르게 비교할 수 있음.

 

 

예시:

arr1 = [4, 5, 8], arr2 = [10, 9, 1, 8], d = 2일 때

 

arr2 = [1, 8, 9, 10] -> arr2 정렬.

 

a = 4 에 대해서 arr2의 중간값인 9와 비교해보면 d보다 큼

-> 그러면 9보다 큰 숫자에 대해서 비교할 필요가 없어지는 것임. d 보다 무조건 클 것이기 때문에

그래서 right를 -1해가며 비교해서 빠르게 구할 수 있음.

 

 

 

5) 

if (diff <= d) return true; // 거리가 d 이하이면 조건에 안 맞는 거 → true 반환

 

- !hasCloseElement(arr2, a, d)일 때 count++이므로 diff <=d 일때는 count 안하기 때문에 true를 반환하면 false이므로 count를 안 하게 되니까 .. true를 반환함.

 

-> 이렇게 조건을 반대로 처리하는 방식이 코드의 흐름을 더 간단하고 직관적으로 만들어 준다는 장점이 있음. 

 

 

6)  

    if (arr2[mid] < a) left = mid + 1;
    else right = mid - 1;


return false;

 

- mid 조정하고 최종적으로 false를 반환해서 true일 때 count 하도록 함.

 

 

 

 

 

.

.

.

이제 이진탐색을 왜 사용하는지 알 것 같음. 

빠르니까 그리고 불필요한 연산 안 해도 되니까.

항상 브루트포스 방식을 사용했는데 이제는 이진 탐색을 사용해서 시간 복잡도를 줄일 수 있는 코드를 더 만들어봐야겠다.