Intersection of Two Arrays II [leetcode]

 

문제 풀이 설명

 

어려운 문제는 아니였다. 그래도 역시 생각보다 오래 고민했다. 한 시간 안되게?

일단 교집합이라고 문제 제목이 나와있기 때문에 단순히 교집합으로 풀어야 겠다 생각하면 안된다.

무구한 삽질을 이미 다른 문제를 통해 경험해 봤기 때문에 python이 제공하는 set 연산을 하면 안된다는걸 알고 있다.

첫번째 케이스의 경우 set 연산으로 수행할 경우 [2,2] 가 아니라 [2]로 나오게 된다.

→ 교집합 연산을 위해서는 리스트가 아니라 집합으로 먼저 바뀌어야 하고 그럼 [1,2,2,1] → [1,2] 로 중복이 제거

나는 이렇게 풀었다 (코드를 보면 알겠지만)

1. 크기가 작은 리스트의 숫자를 꺼낸다.
2. 해당 숫자가 다른 리스트에 들어있는지 판단한다.
3. 들어 있다면 해당 숫자를 크기가 큰쪽에서 제거한 뒤, 교집합 리스트에 추가한다.

크기가 작은 리스트 만 반복해서 보면 되므로 O(n)의 시간이 걸리고, 중복되는 숫자도 체크할 수 있고,

무엇보다 지금까지 푼 문제중에서 (내가 보기에) 코드만 봐도 '아 어떻게 풀었구나' 를 알수 있게 직관적으로 푼거

같아서 뿌듯하다.

 

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

 

문제는 여기서

https://leetcode.com/problems/intersection-of-two-arrays-ii/

Intersection of Two Arrays II - LeetCode