[2024] day 71. Leetcode 349. Intersection of Two Arrays
코딩테스트
2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 3월 10일 (일)
Leetcode daily problem
Leetcode 349. Intersection of Two Arrays
Problem
두 개의 정수 배열 num1, num2가 주어질 때 공통 원소를 반환한다.
반환 시 정렬은 신경쓸 필요 없음!
Solution
set
두 배열을 set 자료형으로 바꿔주고 set에서 제공하는 교집합 찾아주는 함수인 intersection을 사용해서 반환한다.
set을 사용하지 않고 배열의 빈도수를 만드는 맵을 만들고,
찾는 다른 방법도 있다.
그것은 후술
Code
Complexicity
시간 복잡도
해당 배열들을 집합(set) 자료구조로 변환 시킬 때는 배열을 한 번 순회하고 삽입해서 O(n)의 시간이 소요된다.
또 집합을 만든 후에 교집합을 찾을 때 집합의 크기에 영향을 받게 된다.
총 시간 복잡도는 O(min(len(set1), len(set2)) 이다.
공간 복잡도
두 배열을 집합으로 변환해서 사용하기 때문에 O(n+m) 이 발생한다.
n : nums1의 길이 m : num2의 길이이다.
다른 풀이
다른 방법으로 set 을 이용해 배열의 빈도를 파악하지 않고
하나의 배열을 먼저 순회하면서 빈도를 업데이트한 딕셔너리, 맵을 생성한다.
그리고 두 번째 남은 배열을 순회하면서 만들어져 있는 배열 빈도의 맵에서
같은 원소가 있으면 동일 원소이므로 해당 원소를 반환할 결과 리스트에 업데이트하고, 맵에서 해당 원소를 삭제하는 작업을 반복한다.
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
cnt = {}
for num in nums1:
cnt[num] = cnt.get(num, 0)+1
result = []
for num in nums2:
if num in cnt:
result.append(num)
del cnt[num]
return result
해당 코드의 시간복잡도는 첫번째 배열을 탐색하면서 빈도수를 업데이트하므로 O(n)이 소요되고, 두 번째 배열 또한 순차적으로 탐색하므로 O(m)이 소요된다.
즉, O(n+m)이 소요된다.
n : nums1의 길이, m : nums2의 길이
배열을 순회하면서 빈도수 맵을 만드는데 nums1의 고유한 요소의 수에 크기가 비례하게 된다. 최악의 경우 O(n)의 길이를 가질 수 있으므로 공간복잡도는 O(n)이 된다.
