[파이썬 알고리즘 인터뷰][이진검색] 두 배열의 교집합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

두 배열의 교집합 출력

 

책에서 구현된 코드

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()
        # 양쪽 모두 정렬
        nums1.sort()
        nums2.sort()
        i = j = 0
        # 투 포인터 우측으로 이동하며 일치 여부 판별
        while i < len(nums1) and j < len(nums2):
            if nums1[i] > nums2[j]:
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                result.add(nums1[i])
                i += 1
                j += 1

        return result

 

기억해야할 기법

• 포인터 2개로 비교하는 방법도 고려해볼것

 

내가 구현한 코드

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        def bs(nums, target):
            if len(nums) == 0:
                return False
            l = 0
            r = len(nums) - 1
            while l <= r:
                mid = l + (r-l) // 2
                if target < nums[mid]:
                    r = mid-1
                elif target > nums[mid]:
                    l = mid+1
                else:
                    return True
            return False

        nums1 = sorted(set(nums1))
        nums2 = sorted(set(nums2))
        answer = []
        for n in nums1:
            if bs(nums2, n):
                answer.append(n)
        return answer

• 속도는 전체적으로 비슷한듯
  • 탐색하기 전에 set으로 중복을 없애는 것과 중복된 값을 포함한 탐색의 결과를 set에 넣는 속도가 비슷하다