99클럽 코테 스터디 17일차 TIL ✒️두 배열 사이의 거리 구하기

✅ 오늘의 학습 키워드

• 완전 탐색
• 이진 탐색

---

🔍 오늘의 문제 분석

↘️ 오늘의 문제 바로가기 ↘️

 

• 두 정수 배열과 정수가 주어진다
• 두 정수 배열의 각 요소의 거리가 정수 d보다 큰 경우를 카운트한다
• 정수 배열의 길이는 500 이하이고 정수 d는 100 이하이다

 

 

 

---

✨ 오늘의 회고

📌내가 적은 답안📌

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int count=0;
        for(int i=0; i<arr1.length; i++){
            boolean b = false;

            for(int j=0; j<arr2.length; j++){
                if((Math.abs(arr1[i]-arr2[j])) <= d) {
                    b = true;
                    break;
                }
            }
            
            if(!b) count++;
        }
        return count;
    }
}

이중 반복문을 사용하고 두 배열의 값을 모두 비교해서 조건을 찾도록 했다. 만약 arr1의 i번째 요소와 arr2의 j번째 요소의 차이가 d 이하이면 boolean을 true로 설정하고 반복문을 종료하도록 했다. arr2 배열 내 요소를 비교한 이후에도 boolean이 false라면 문제의 요구사항에 맞기 때문에 count를 증가하도록 했다. 이 방법은 모든 요소를 반복문으로 검사하기 때문에 완전 탐색이 되고, 시간 복잡도는 O(n * m)가 된다.

 

추가로 이진 탐색으로 푼 방법이 있어 참고해 보았다.

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        
        int count = 0;
        for (int num : arr1) {
            if (!check(arr2, num - d, num + d)) {
                count++;
            }
        }
        return count;
    }
    
    private boolean check(int[] arr, int min, int max) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] >= min && arr[mid] <= max) {
                return true;
            } else if (arr[mid] < min) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}