코딩테스트 문제 (3) - 두 배열의 교집합

두 배열의 교집합을 찾는 문제입니다. 중복된 문자는 고려하지 않고 한 문자로 취급합니다. 

문제

1. array1 = [1,2,2,1], array2 = [2,2]
=> [2]

2. array1 = [4,9,5], array2 = [9,4,9,8,4]
=> [9,4]

 

풀이

array1과 array2에 대해 이중 for 루프를 돌면서 결과 집합 (파이썬의 set)에 추가하면 될 것 같습니다. 하지만 array 2개의 루프를 수행하니 시간 복잡도는 $O(n^2)$가 되겠네요. 더 작은 시간 복잡도가 걸리는 방법은 뭘까요?

array1에 대해서는 그대로 for 루프를 수행하고 for 루프 안에서 해당 array1의 값을 array2에 대해 이진 탐색으로 값을 검색하면 어떨까요? 이진 탐색은 시간 복잡도가 $O(\log n)$이므로 알고리즘의 시간 복잡도는 n을 곱해 $O(n\log n)$이 되겠네요.

kaggle.com 의 notebook으로 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 난이도: 하

참조

• <파이썬 알고리즘 인터뷰>, p529-531
• leetcode.com/problems/intersection-of-two-arrays/