[Leetcode/Set, TwoPointer] 349. Intersection of Two Arrays

풀이1) set  자료구조 사용

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

시간 복잡도 분석

• set(nums1): O(N)
• set(nums2): O(M)
• set1 & set2: O(min(N, M))
• list(...): O(K) (교집합 원소 수를 K라고 가정)

➡️ 최종 시간 복잡도: O(N + M) (매우 효율적)

---

풀이2) two-pointer 사용

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()  # nums1 정렬
        nums2.sort()  # nums2 정렬
        i, j = 0, 0   # 투 포인터 초기화
        result = set() # 중복 방지를 위한 set 사용
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:  # nums1이 작으면 i 증가
                i += 1
            elif nums1[i] > nums2[j]:  # nums2가 작으면 j 증가
                j += 1
            else:  # 두 값이 같으면 결과에 추가하고, i와 j 모두 증가
                result.add(nums1[i])
                i += 1
                j += 1
        
        return list(result)  # 최종 결과 반환

📌 Two-pointer 풀이 방법

1. 두 배열 nums1과 nums2를 오름차순 정렬한다.
2. 두 개의 포인터 i와 j를 각각 nums1과 nums2의 첫 번째 요소에서 시작한다.
3. 두 포인터를 이동하면서 다음 규칙을 적용한다:
   • nums1[i] < nums2[j]: i를 증가 (nums1의 값이 작으므로 더 큰 값을 찾아야 함)
   • nums1[i] > nums2[j]: j를 증가 (nums2의 값이 작으므로 더 큰 값을 찾아야 함)
   • nums1[i] == nums2[j]: 같은 값이므로 결과 result에 추가하고, i와 j를 모두 증가
4. 중복된 값을 피하기 위해 result는 set으로 관리한다.
5. 최종적으로 list(result)를 반환한다.

🔹 시간 복잡도 분석

1. 정렬 단계: nums1.sort()와 nums2.sort()는 각각 O(N log N)과 O(M log M).
2. 투 포인터 탐색: O(N + M) (두 배열을 한 번씩 순회).

➡ 총 시간 복잡도: O(N log N + M log M) (정렬 때문에 set 방법보다 느릴 수 있음)