[LeetCode] 349. Intersection of Two Arrays

1. 문제 이해

두 배열이 주어진다.

두 배열의 교집합을 구한다.

 

 

2. 풀이 과정

한쪽 배열은 순서대로 탐색하고 다른 한쪽 배열은 정렬해서 Binary Search로 값을 찾는다.

첫 번째 방법은 Binary Search를 직접 구현하는 것이다.

704번 문제와 거의 동일하게 구현한다. target 매개변수만 추가한다.

def binary_search(a:int, b:int, target) -> int:
    if a > b:
        return -1
    mid = (a+b)//2
    if target == l1[mid]:
        return mid
    if target > l1[mid]:
        return binary_search(mid+1, b, target)
    elif target < l1[mid]:
        return binary_search(a, mid-1, target)

 

정답에 중복된 값이 들어가는 것을 방지하기 위해 set 자료형을 사용한다.

ans: Set = set()
for k in nums2:
    idx = binary_search(0, len(l1)-1, k)
    if idx != -1:
        ans.add(l1[idx])

 

두 번째 방법은 Binary Search 기반으로 리스트에 값을 삽입할 위치를 찾는 Python의 bisect 모듈을 사용하는 것이다.

ans: Set = set()
nums1.sort()
for n1 in nums2:
    i2 = bisect.bisect_left(nums1, n1)
    if len(nums1) > 0 and len(nums1) > i2 and n1 == nums1[i2]:
        ans.add(n1)

 

 

3. 전체 코드

(첫 번째 풀이)

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        l1 = sorted(nums1)
        
        def binary_search(a:int, b:int, target) -> int:
            if a > b:
                return -1
            
            mid = (a+b)//2
            if target == l1[mid]:
                return mid
            
            if target > l1[mid]:
                return binary_search(mid+1, b, target)
            elif target < l1[mid]:
                return binary_search(a, mid-1, target)
        
        ans: Set = set()
        for k in nums2:
            idx = binary_search(0, len(l1)-1, k)
            if idx != -1:
                ans.add(l1[idx])
        
        return ans

 

(두 번째 풀이)

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans: Set = set()
        nums1.sort()
        for n1 in nums2:
            i2 = bisect.bisect_left(nums1, n1)
            if len(nums1) > 0 and len(nums1) > i2 and n1 == nums1[i2]:
                ans.add(n1)
        return ans

 

 

4. 생각할 점

- 한쪽 배열만 정렬하고 Binary Search를 이용해 교집합을 찾는다는 발상

- Python의 bisect 모듈에는 Binary Search가 구현되어 있다.

 

 

5. 출처

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

- 박상길, 파이썬 알고리즘 인터뷰, 책만, 2020