350. Intersection of Two Arrays II

중복을 허용하는 교집합을 구하는 문제다.

Solution

1. set에 넣어 교집합 연산을 수행한다.
2. 교집합 set에 들어간 요소의 개수를 두 배열 중 최솟값으로 추가한다.

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        a = set(nums1)
        b = set(nums2)
        s = a & b # 교집합
        ans = []
        for num in s:
            count = min(nums1.count(num), nums2.count(num))
            ans.extend([num] * count) # 개수를 세서 그만큼 배열에 추가

        return ans

extend() : 각각의 원소들을 추가한다.

• append()는 x 그 자체를 원소로 넣고 extend()는 각 항목들을 넣는다.
• 문자열인 경우에는 문자열의 각 알파벳을 넣는다.

시간 복잡도

1. set을 만드는 시간 복잡도는 각 배열의 길이에 비례한 O(n), O(m)
2. 교집합을 구하는 시간 복잡도는 O(n + m)
3. 각 요소를 리스트에 추가하는 시간 복잡도는 O(min(n, m))

따라서 전체적으로 시간 복잡도는 O(n + m) 이다.