[LeetCode] Array > Intersection of Two Arrays II

leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/674/

Explore - LeetCode

---

풀이

처음에는 그냥 set자료형의 intersection 함수를 사용하였지만, 반례로 [1,2,2,1] , [2,2]가 존재하였다. 중복되는 숫자가 사라지기 때문에 정확한 교집합을 구할 수 없음.

 

다음으로는 단순하게 반복문을 돌면서 해당 숫자가 배열에 존재하는지를 in을 통해 검사하였는데, 이미 검출된 교집합이 다시 검출되는 반례가 존재했다. [2,2,2,2] , [2]

 

따라서 배열에 존재하는지를 in을 통해 검사하고, 존재한다면 해당 배열에서 remove해주는 식으로 문제를 해결하였다.

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        answer = []
        if len(nums1) < len(nums2):
            for i in nums1:
                if i in nums2:
                    answer.append(i)
                    nums2.remove(i)
        else:
            for i in nums2:
                if i in nums1:
                    answer.append(i)
                    nums1.remove(i)
        return answer