[Swift] 배열의 유사도 회고

안녕하세요! 피피아노입니다 🎵

 

이번 포스팅에서는 제가 배열 유사도 확인 코드를 공부하면서 잘못된 부분에 대해서 회고(?)하는 포스팅을 작성해보려고 합니다.

 

그럼 바로 시작하겠습니다!

 

배열의 유사도

일단 제가 풀려고 했던 문제는 배열 s1과 s2가 주어졌을 때 같은 원소의 개수를 return 하도록 함수를 작성하는 문제입니다.

 

예를 들어서 s1 배열에는 ["a", "b", "c"]가 존재하고 s2 배열에는 ["b", "c", "d"]가 존재한다고 하면 같은 원소는 b와 c이니까 return값이 2가 나오도록 말이죠.

 

그래서 저는 먼저 count변수를 선언하고 filter함수를 사용해서 중복이 있을 때마다 count 변수 값을 1씩 증가시키려고 했습니다.

 

내가 해결한 방식

import Foundation

func solution(_ s1: [String], _ s2: [String]) -> Int {
    return s1.filter { s2.contains($0) }.count
}

이렇게 말이죠!

 

발생한 문제!

여기까지는 아무 문제없다고 생각했지만....

 

시간 복잡도를 간과하고 있었습니다...

 

물론 아직 코테 공부를 시작한 지 정말 정말 정말 얼마 안 되어서 구현하는 것에 의미를 두느라 시간 복잡도까지 신경 쓸 여유가 없었지만 그래도 한번쯤은 생각했어야 했는데.....😭

 

해당 방식으로도 충분히 문제를 해결할 수는 있지만 filter와 contains를 함께 사용할 때 배열의 모든 요소에 대해 contains가 한 번씩 호출되기 때문에 문제가 발생했던 겁니다..! 이 방식은 시간 복잡도가 O(n \times m)로, s1과 s2의 크기가 클수록 효율이 떨어지게 된다고 하더군요...

 

개선한 방식

그래서 시간 복잡도를 해결할 수 있는 방법이 뭐가 있을까 공부하다가 Set 함수에 대해서 알게 되었습니다. Set의 contains는

O(1)이므로 전체 시간 복잡도가 O(n + m)으로 개선된다고 하더군요!

 

Set 함수를 적용한 코드는 아래처럼 작성할 수 있었습니다.

import Foundation

func solution(_ s1: [String], _ s2: [String]) -> Int {
    let set1 = Set(s1)
    let set2 = Set(s2)
    return set1.intersection(set2).count
}

(엄청 간단하네......)

 

간단하게 설명을 해보자면 s1과 s2를 각각 Set으로 변환하여 set1과 set2로 저장하였습니다.

 

Set은 중복된 값을 허용하지 않는 컬렉션이기 때문에, 이 과정에서 s1과 s2의 중복 요소가 자동으로 제거됩니다.

 

그리고 set1.intersection(set2)는 set1과 set2의 교집합을 반환합니다. 즉, s1과 s2에 모두 포함된 요소들만 남깁니다.

마지막으로 .count를 사용하여 교집합의 요소 개수를 계산하고, 그 값을 반환합니다.

 

이렇게 코드를 수정했더니 아무 문제 없이 통과가 되었습니다!

 

느낀 점

기능을 구현하느라 급급해서 시간복잡도는 크게 신경 쓰지 못했는데 이번 문제를 통해서 시간복잡도의 중요성을 느낄 수 있었고 Set과  intersection 메서드에 대해서도 알게 되고 공부할 수 있던 기회라서 도움이 많이 되었던 것 같습니다.

 

Set과 intersection메서드에 대해서는 추후에 따로 정리를 해서 포스팅을 해보려고 합니다!

---

감사합니다.

 

잘못된 내용이 있거나 더 좋은 내용 피드백은 언제나 환영합니다!

궁금하신 부분은 댓글로 질문 부탁드립니다!