[이진 검색] 두 배열의 교집합

349 | Intersection of Two Arrays
https://leetcode.com/problems/intersection-of-two-arrays/

 

 

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

 

 

Example 1:

 

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

 

Example 2:

 

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

 

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

 

작성 코드

 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        intersection = []
        
        nums1 = list(set(nums1))
        nums2 = list(set(nums2))
        
        for n in nums1:
            if n in nums2:
                intersection.append(n)
            
        return intersection

 

• 중복 제거하기 위해 set 변환, for 문을 돌고 in 연산을 사용하기 위해 list 변환
• 통과는 했지만 이진 검색을 이용한 풀이는 아님

 

 

참고 코드

 

브루트 포스로 계산

 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()
        for n1 in nums1:
            for n2 in nums2:
                if n1 == n2:
                    result.add(n1)

        return result

 

• nums1, nums2 배열을 돌며 하나하나 비교 
• 교집합, 즉 중복 없이 return 해야하기 때문에 return 할 result 는 set 으로 생성
• 비효율적 : O(n^2)

 

 

이진 검색으로 일치 여부 판별

 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()
        nums2.sort()
        for n1 in nums1:
            # 이진 검색으로 일치 여부 판별
            i2 = bisect.bisect_left(nums2, n1)
            if len(nums2) > 0 and len(nums2) > i2 and n1 == nums2[i2]:
                result.add(n1)

        return

 

• O(nlogn) : O(n) + O(logn) (이진 검색)
• bisect_left : 정렬된 순서를 유지하도록 a에 x를 삽입할 위치를 찾는 함수, x가 a에 이미 있으면, 삽입 위치는 기존 항목 앞(왼쪽)이 됨
• len(nums2) > 0 : nums2 가 비어있을 경우 ? 근데 없어도 통과는 됨 ! 애초에 문제 조건이 ' 1 <= nums1.length, nums2.length <= 1000 ' 라 비어있을 경우는 생각 안 해도 됨
• len(nums2) > i2 : [1,2] [1,1] 가 입력되었을 경우 n1 에 2가 들어갔을 때 i2 값은 2가 됨 (인덱스가 2) 그럼 indexError 뜸
• n1 == nums2[i2] : 원소가 두 집합에 다 있다면!!