leetcode 349. Intersection of Two Arrays

문제

https://leetcode.com/problems/intersection-of-two-arrays/description/

1차 코드

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let nums1Set = Set(nums1)
        let nums2Set = Set(nums2)
        if nums1Set.count < nums2Set.count {
            return loopForIntersection(nums2Set, nums1Set)
        } else {
            return loopForIntersection(nums1Set, nums2Set)
        }
    }
    
    private func loopForIntersection(_ loopNums: Set<Int>, _ comparedNums: Set<Int>) -> [Int] {
        var results: [Int] = []
        for num in loopNums {
            guard comparedNums.contains(num) else { continue }
            results.append(num)
        }
        return results
    }
}

개선 코드

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        Array(Set(nums1).intersection(Set(nums2)))
    }
}

거두절미하고, 일단 Set 타입에서는 교집합 메서드를 기본적으로 제공해주고 있었다…!!

@inlinable
public __consuming func intersection(_ other: Set<Element>) -> Set<Element> {
    Set(_native: _variant.intersection(other))
}

그래도 시간복잡도, 공간복잡도, 실행속도 측면에서 차이가 없었다!

⏱️ 시간복잡도

• 두 코드 모두 [Int]를 Set<Int>로 변환하는 과정에서 O(n) + O(m) 시간복잡도가 발생합니다.
• loopForIntersection(::) 에서 contains의 O(1) 시간복잡도가 반복문으로 발생하므로 O(k), 즉 최악의 경우 O(max(n,m)) 시간복잡도가 발생합니다.
• intersection(_:) 교집합 메서드 또한 O(max(n,m)) 시간복잡도가 발생합니다.
• 전체적으로 두 코드 모두 O(n+m) 시간복잡도가 발생합니다.

📦 공간복잡도

• 두 개의 Set 집합으로 인해 O(n) + O(m) 공간복잡도가 발생합니다.
• 결과로 반환하기 위해 생성되는 [Int]은 최악의 경우 O(min(n,m)) 공간복잡도가 발생합니다.
• 전체적으로 두 코드 모두 O(n+m) 공간복잡도가 발생합니다.

🧹 가독성 개선

1. 1차 코드에서 파라미터명을 좀 더 명확하게 수정할 수 있습니다.

private func loopForIntersection(of smaller: Set<Int>, with larger: Set<Int>) -> [Int] {
	var results: [Int] = []
	for num in smaller {
		guard larger.contains(num) else { continue }
		results.append(num)
	}
	return results
}