LeetCode - 349. Intersection of Two Arrays [Python]

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

Intersection of Two Arrays - LeetCode

---

풀이 과정

두 배열의 교집합을 구하는 문제이다.

 

리스트를 set 자료형으로 바꾼다음에 s1.intersection(s2) 혹은 s1 & s2로 파이썬 내장 함수를 이용하는 방법이 가장 편리한 풀이방법이다.

 

O(N^2) 방법으로 브루트 포스로도 풀 수는 있다.

 

자료형 내장 함수도, 브루트 포스도 싫다! 하면 두 리스트를 모두 정렬후 투 포인터로 문제를 해결하면 된다.

 

포인터 2개 설정하고 맨 앞에 포인터를 설정한 뒤 포인터가 가리키고 있는 값끼리 비교하고, 같으면 정답에 추가, 한 쪽이 작으면 작은쪽의 포인터를 한 칸 전진하는 방법으로 문제를 해결할 수 있다.

---

소스 코드

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        answer = set()
        nums1.sort()
        nums2.sort()
        len1 = len(nums1)
        len2 = len(nums2)
        index1 = 0
        index2 = 0
        
        while index1 < len1 and index2 < len2:
            if nums1[index1] < nums2[index2]:
                index1 += 1
            elif nums1[index1] > nums2[index2]:
                index2 += 1
            else:
                answer.add(nums1[index1])
                index1 += 1
                index2 += 1
        
        return answer

 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1 = set(nums1)
        nums2 = set(nums2)
        return nums1 & nums2