# 99클럽 코테 스터디 17일차 TIL - 두 배열 사이의 거리 값 찾기

오늘의 문제: 1385번 Find the Distance Value Between Two Arrays

---

🤔 문제 분석 및 초기 접근

두 개의 정수 배열 arr1, arr2와 정수 d가 주어질 때, '거리 값'을 계산하는 문제이다.

거리 값의 정의: arr1의 요소 arr1[i] 중에서, arr2의 모든 요소 arr2[j]에 대해 |arr1[i] - arr2[j]| > d 를 만족하는 arr1[i]의 개수.

즉, arr1의 각 요소를 arr2의 모든 요소와 비교해서, 그 차이의 절대값이 한 번이라도 d 이하가 되면 안 된다. 이 조건을 통과하는 arr1 요소의 개수를 세는 것이 목표다.

초기 접근: 문제 정의를 그대로 코드로 옮겨보자.
arr1의 각 요소 a에 대해, arr2의 모든 요소 b가 abs(a - b) > d 조건을 만족하는지 확인하면 된다. Swift의 고차함수를 사용하면 간결하게 표현할 수 있겠다 싶었다.

// 초기 제출 코드
func findTheDistanceValue(_ arr1: [Int], _ arr2: [Int], _ d: Int) -> Int {
    // arr1의 각 요소 a에 대해 필터링
    return arr1.filter { a in
                // arr2의 모든 요소 b가 |a - b| > d 조건을 만족하는지 확인
                arr2.allSatisfy { b in abs(b - a) > d }
            }.count // 조건을 만족하는 요소들의 개수 반환
}

---

💡 문제점(?) 발견 및 개선 아이디어

위 코드는 직관적이고 문제 정의를 잘 반영한다. 제출 결과도 놀랍게 0ms가 나왔다!
하지만 이 코드의 시간 복잡도를 생각해보면, arr1의 각 요소(n개)마다 arr2의 모든 요소(m개)를 순회하며 allSatisfy 연산을 수행하므로, 시간 복잡도는 O(n * m) 이다. 즉, 이중 for문과 동일한 복잡도이다.

n과 m의 최대 크기가 500이므로, 최악의 경우 500 * 500 = 250,000번의 연산이라 LeetCode에서는 통과할 수 있지만, 만약 데이터 크기가 더 커진다면 비효율적일 수 있다.

"어떻게 하면 더 좋은 코드가 될 수 있을까?" 라는 고민이 들었다.
O(n*m)보다 효율적인 방법은 없을까?

개선 아이디어: arr2를 미리 정렬해두면 어떨까?
arr2가 정렬되어 있다면, arr1의 각 요소 a에 대해 arr2에서 a - d 와 a + d 사이의 값이 존재하는지 빠르게 확인할 수 있다. 즉, arr2 내에 a - d <= b <= a + d 를 만족하는 요소 b가 하나라도 있는지 이진 탐색(Binary Search) 으로 찾아보는 것이다. 만약 해당 범위 내의 요소가 arr2에 없다면, 그 a는 거리 값을 증가시키는 요소가 된다.

---

🔄 코드 개선 및 최종 (개념적) 코드

arr2를 정렬하고 이진 탐색을 활용하는 방식으로 개선할 수 있다.

1. arr2를 오름차순으로 정렬한다. (시간 복잡도: O(m log m))
2. arr1의 각 요소 a에 대해 다음을 수행한다. (시간 복잡도: O(n))
   • arr2에서 a - d 와 a + d 사이의 값이 존재하는지 이진 탐색으로 확인한다. (시간 복잡도: O(log m))
     • 이진 탐색을 직접 구현하거나, 특정 값(a - d 또는 a + d)의 위치를 찾는 방식으로 응용할 수 있다.
     • 예: arr2에서 a - d보다 크거나 같은 첫 번째 요소의 인덱스 lowerBound와 a + d보다 큰 첫 번째 요소의 인덱스 upperBound를 찾는다. 만약 lowerBound가 유효하고 arr2[lowerBound]가 a + d 이하이면, 범위 내 요소가 존재하는 것이다.
   • 만약 a - d 와 a + d 사이의 요소가 arr2에 존재하지 않으면 결과 카운트를 1 증가시킨다.
3. 최종 카운트를 반환한다.

이 방식의 전체 시간 복잡도는 O(m log m + n log m) 이 되어, O(n * m)보다 효율적이다.

// 개선된 로직 (이진 탐색 활용 - 직접 구현 필요)
func findTheDistanceValue_Optimized(_ arr1: [Int], _ arr2: [Int], _ d: Int) -> Int {
    // 1. arr2 정렬
    let sortedArr2 = arr2.sorted()
    var distanceValue = 0

    // 2. arr1 순회
    for a in arr1 {
        // 3. arr2에서 a - d 와 a + d 사이 값 존재 여부 확인 (이진 탐색)
        var foundInRange = false
        var left = 0
        var right = sortedArr2.count - 1
        
        // 간단한 이진 탐색 예시 (범위 내 값 존재 여부만 확인)
        while left <= right {
            let mid = left + (right - left) / 2
            let b = sortedArr2[mid]
            
            if abs(a - b) <= d { // 범위 내 값 발견!
                foundInRange = true
                break
            } else if b < a - d { // 중간값이 목표 범위보다 작으면, 오른쪽 탐색
                left = mid + 1
            } else { // 중간값이 목표 범위보다 크면, 왼쪽 탐색
                right = mid - 1
            }
        }
        
        // 범위 내 값이 없었으면 카운트 증가
        if !foundInRange {
            distanceValue += 1
        }
    }

    return distanceValue
}

참고: 위 이진 탐색 로직은 특정 값 하나를 찾는 것이 아니라 범위 내 값 존재 여부를 확인하는 것이므로, 정확한 구현은 조금 더 다듬어야 할 수 있다. 예를 들어, lower_bound를 찾는 방식으로 접근하는 것이 더 정확할 수 있다.

---

✅ 회고 및 배운 점

• 문제 요구사항을 직관적으로 코드로 옮기는 능력도 중요하지만(filter + allSatisfy), 시간 복잡도를 분석하고 개선 방안을 고민하는 습관을 들여야겠다.
• O(n*m) 솔루션이 LeetCode에서 통과되더라도(데이터 제약 조건 덕분에), 더 효율적인 알고리즘(정렬 + 이진 탐색 O(n log m + m log m))을 떠올리고 구현할 수 있는지 점검하는 것이 중요하다.
• 특정 값의 존재 여부가 아니라, 특정 범위 내의 값 존재 여부를 빠르게 확인해야 할 때, 대상 배열을 정렬하고 이진 탐색을 활용하는 것이 효과적인 전략임을 다시 한번 확인했다.
• Swift의 allSatisfy는 컬렉션의 모든 요소가 특정 조건을 만족하는지 검사할 때 매우 유용하다.

---