[LEETCODE] 350: Intersection of Two Arrays II(Python)

Intersection of Two Arrays II - LeetCode

문제 설명

두 배열의 교집합을 구해보자. 만약 동일한 교집합 원소가 여러 개라면 중복도 포함해서 출력해야 한다.

나의 풀이

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        answer=[]
        d1=dict()
        d2=dict()
        
        for i in nums1:
            d1[i]=d1.get(i,0)+1
            
        for i in nums2:
            d2[i]=d2.get(i,0)+1
            
        for k,v in d1.items():
            if k in d2:
                j=min(v,d2[k])
                answer.extend([k]*j)
            
        return answer

두 배열의 각 원소별 빈도수를 딕셔너리에 저장하고, 하나의 딕셔너리를 기준으로 다른 딕셔너리에도 있는지 확인하면서 교집합을 체크했다.

시간복잡도

딕셔너리를 만드는 데 O(2*n), 원소가 교집합인지 검사하는 부분에서 O(n)이지만 extend에서 최대 O(n)이 나올 수 있기 때문에 전체 시간복잡도는 O(n^2)이다.