[알고리즘/leetcode] Intersection of Two Arrays II(python)

처음에 문제 이해를 잘못해서 연속된 배열만 가능한 줄 알았는데 그냥 교집합 구하면 된다.

set의 intersection을 먼저 떠올리겠지만 set은 중복이 불가능해서 다른 방법을 찾아야 함

그래서 nums1의 숫자 개수를 각각 세어서 딕셔너리로 만들고 nums2에서 하나씩 빼면서 찾으면 된다.

편하게 하려면 collections.Counter() 사용!

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) < len(nums2):
            nums1, nums2 = nums2, nums1
            
        # a = collections.Counter(nums1)
        a = {}
        for i in nums1:
            if i not in a:
                a[i] = 1
            else:
                a[i] += 1
        ans = []
        for i in nums2:
            if i in a and a[i]:
                ans.append(i)
                a[i] -= 1
                if not a[i]:
                    del a[i]
        return ans