leetcode 1385. Find thd Distance Value Between Two Arrays 문제 풀이

문제

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

문제 이해

일단 문제 이해부터.

arr1[i]에 대해, `|arr1[i]-arr2[j] <= d`가 해당되는 arr2[j]가 없어야 한다.

 

즉, |arr1[i]-arr2[j]| <= d가 성립되는 arr1의 원소 개수를 카운팅해야한다.

1차 코드

class Solution {
    func findTheDistanceValue(_ arr1: [Int], _ arr2: [Int], _ d: Int) -> Int {
        var count = 0
        for a1 in arr1 {
            guard meetTheCondition(a1, arr2, d) else { continue }
            count += 1
        }
        return count
    }
    
    private func meetTheCondition(_ a1: Int, _ arr2: [Int], _ d: Int) -> Bool {
        for a2 in arr2 {
            guard abs(a1-a2) <= d else { continue }
            return false
        }
        return true
    }
}

어떻게 개선할 수 있을까?

class Solution {
    func findTheDistanceValue(_ arr1: [Int], _ arr2: [Int], _ d: Int) -> Int {
        let sortedArr2 = arr2.sorted()
        var counts = 0
        for a1 in arr1 {
            let index = sortedArr2.binarySearchInsertPosition(of: a1)
            if index < sortedArr2.count, abs(sortedArr2[index]-a1) <= d {
                continue
            }
            if index > 0, abs(sortedArr2[index-1]-a1) <= d {
                continue
            }
            counts += 1
        }
        return counts
    }
}

extension Array where Element == Int {
    func binarySearchInsertPosition(of target: Int) -> Int {
        var low = 0, high = count
        // 점점 좁혀가며 정렬상 target이 있어야 할 위치 찾기
        while low < high {
            let mid = (low + high) / 2
            if self[mid] < target {
                // 시작점 변경
                low = mid + 1
            } else {
                // 끝점 변경
                high = mid
            }
        }
        return low
    }
}

Solution().findTheDistanceValue([4,5,8], [10,9,1,8], 2)

🔑 키워드 : 이분탐색(Binary Search) = 이진탐색

• 정의 : 정렬된 배열에서 원하는 값을 빠르게 찾기 위해, 배열을 반씩 나누어 탐색 범위를 좁혀 나가는 알고리즘
• 동작 원리 : low와 high를 mid 기준으로 반씩 좁혀가는 원리

처음 이분탐색 정의만 보고 코드를 개선하려 했을 때에는, mid 포인트만 잡고 배열을 반씩 나누면서 갱신하는 것이라고 생각했습니다. 그러나 low와 high를 갱신하면서 mid에 위치한 값을 통해 타겟이 정렬된 배열 상 위치할 수 있는 인덱스를 반환하는 것이 해당 문제에서 이분탐색을 적용한 동작 원리였어요!
그리고 이분탐색을 통해 정렬된 배열 사이에 비교값이 위치할 수 있는 인덱스를 통해 왼쪽/오른쪽 원소와의 조건식 검증을 통해 문제를 풀 수 있습니다.

⏱️ 시간복잡도

• 개선 전
  두 개의 반복문이 중첩되기 때문에 전체적인 시간복잡도는 O(n*m)
• 개선 후
  arr2 정렬 → O(m log m)
  이분탐색으로 target이 정렬될 위치를 찾는 과정 → O(log m) → arr1만큼 반복되어 O(n log m)
  전체적인 시간복잡도는 O(m log m) + O(n log m)

📦 공간복잡도

• 개선 전
  입력 배열 외에 별도 공간을 할당하지 않기 때문에 O(1)
• 개선 후
  정렬된 배열을 복사함으로써 O(m)