[리트코드] Intersection of Two Arrays(python)

리트코드, Intersection of Two Arrays_투 리스트의 교집합

Intersection of Two Arrays - LeetCode

TL;DR

• 이진 탐색(Binary search)

문제 요약

1. 두 정수 리스트 nums1과 nums2가 주어질 때, 두 리스트의 교집합을 반환하는 함수를 작성하라.
2. 교집합에 포함되는 원소들은 유일해야 하며, 순서는 상관없다.

 

- 주어진 두 리스트에 공통 원소를 반환하는 함수를 작성하면 된다. 주어진 제한에 따라 중복된 원소들은 교집합에 넣을 때 한 번만 처리해야 한다.

입출력 형태

입출력 예시

 

예시 1 :: 두 리스트에 공통적으로 있는 원소는 [2, 2]이다. 문제 조건에 따라 중복된 값을 한 번만 처리하여 [2]가 정답이 된다.

예시 2 :: 두 리스트에 공통적으로 있는 원소는 [9, 4]이다. 마찬가지로 문제 조건에 따라 한 번만 처리하여 [9, 4]가 정답이 된다. 문제에서는 순서는 상관없다고 하였으므로 주어진 것과 같이 [4, 9]도 정답이 된다.

풀이

이 문제는 여러 방법으로 풀어보았다. 첫 번째는 완전 탐색을 사용한 방법이다.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        answer = []
        for num in nums1:
            if num in nums2 and num not in answer:
                answer.append(num)
        return answer

 

nums1을 조회하며 원소가 nums2에 있으면서 교집합을 저장할 리스트에 존재하지 않는지 확인하여 조건을 만족할 경우 정답 리스트에 삽입한다. 문제를 그대로 해석해서 푼 문제이다.

 

Binary search를 사용한 방법으로도 문제를 해결할 수 있다.

Binary search은 `bisect`를 사용하는 방법과 직접 구현하는 방법을 사용할 수 있는데 두 가지 모두로 푼 답을 공유한다.

먼저 `bisect`를 사용해서 푼 문제이다. bisect_left는 binary search를 수행할 반복 가능한 변수(리스트 등)과 원하는 값이 매개변수로 주어진다. 이 메소드는 리스트 내에서 원하는 값을 정렬된 순서를 유지하며 삽입할 수 있는 인덱스 위치를 반환해준다. Binary search를 수행할 때 bisect_left의 결과로 얻은 인덱스가 원하는 값과 같은지 여부를 통해 문제 해결에 응용할 수 있다.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        import bisect
        answer = set()
        nums2.sort()
        
        for num1 in nums1:
            index = bisect.bisect_left(nums2, num1)
            
            if index < len(nums2) and nums2[index] == num1:
                  answer.add(num1)
        return answer

 

bisect_left를 사용하기 위해서는 우선 대상이 되는 리스트가 정렬이 되어 있어야 한다. 그렇기 때문에 nums2의 정렬을 수행해준다.

그리고 nums1을 순회하며 각 원소들이 nums2에 존재하는지 확인한다. 이 때, bisect_left에서 해당 값이 존재한다면 해당 값의 인덱스를 반환할 것이고 그렇지 않다면 삽입할 수 있는 위치를 반환할 것이다. nums2의 길이를 초과하지 않는 선에서 얻어낸 index의 값이 num1과 같다면 두 리스트 모두에 존재하는 원소라고 할 수 있기 때문에 정답 집합(set)에 추가한다.

리스트로 정답을 선언한 전 풀이와 달리 중복된 원소 체크하는 부분을 없애기 위해 정답의 타입을 집합으로 선언하였다.

 

다음 풀이는 `bisect`를 사용하지 않고 binary search를 직접 구현한 방법이다.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums2.sort()
        
        for num1 in nums1:
            low, high = 0, len(nums2) - 1
            while low <= high:
                mid = (low + high) // 2
                
                if nums2[mid] == num1:
                    answer.add(num1)
                    break
                elif nums2[mid] < num1:
                    low = mid + 1
                else:
                    high = mid - 1
                
        return answer

 

bisect를 사용한 풀이와 마찬가지로 nums1을 순회하며 해당 원소가 nums2에 있는지 binary search를 통해 확인한다. 만약 nums2에도 존재한다면 정답 집합에 추가한다.

 

보통 binary search의 경우 시간 복잡도로 O(logn)이 소모된다고 말한다. 이 문제의 경우는 nums1을 순회하며 binary search를 수행하기 때문에 시간 복잡도가 O(nlogn)이라고 말할 수 있다.

리트코드에서 같은 코드를 동일하게 수행하더라도 매번 런타임이 달리지지만 완전 탐색과 binary search를 사용했을 때의 런타임 차이를 첨부하자면 아래 그림과 같다.

(위) Binary search (아래) 완전 탐색