[LeetCode] - 349. Intersection of Two Arrays
LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Intersection of Two Arrays" 문제입니다.
--> https://leetcode.com/problems/intersection-of-two-arrays/description/
문제 :
Given two integer arrays nums1 and nums2, return an array of their intersection .
Each element in the result must be unique and you may return the result in any order.
Example 1 :
Input : nums1 = [1,2,2,1], nums2 = [2,2]
Output : [2]
Example 2 :
Input : nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output :[9,4]
Explanation : [4,9] is also accepted.
Constraints :
- 1 <= nums1.length, nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 1000
두 개의 정수 배열 nums1과 nums2가 주어질 때, 이들의 교집합을 구하는 문제입니다. 교집합이란 두 배열에서 공통으로 존재하는 요소를 말하며, 결과 배열의 각 요소는 유일해야 합니다. 또한, 결과 배열의 순서는 상관없습니다.
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2 = nums2.length;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < n1; i++) {
set.add(nums1[i]);
}
HashSet<Integer> intersec = new HashSet<>();
for (int i = 0; i < n2; i++) {
if (set.contains(nums2[i])) {
intersec.add(nums2[i]);
}
}
int[] res = new int[intersec.size()];
int x = 0;
for (int i : intersec) {
res[x] = i;
x++;
}
return res;
}
}
이 코드는 두 정수 배열 nums1과 nums2의 교집합을 구하는 방법을 구현한 것입니다. 교집합을 구하는 과정에서 각 요소는 유일하게 나타나야 하며, 결과의 순서는 중요하지 않습니다.
- 변수 초기화 :
- n1과 n2는 각각 배열 nums1과 nums2의 길이를 저장하는 변수입니다.
- 첫 번째 배열의 요소를 Set에 저장 :
- nums1의 모든 요소를 set이라는 HashSet에 추가합니다. 이 과정은 중복을 제거하는 효과가 있습니다.
- 교집합 계산 :
- nums2의 각 요소가 set에 존재하는지 확인합니다.
- 존재한다면, 해당 요소를 intersec이라는 새로운 HashSet에 추가합니다. 이로 인해 intersec은 nums1과 nums2의 교집합을 가지게 됩니다.
- 결과 배열로 변환 :
- intersec의 요소를 순회하며 res 배열에 추가합니다.
- 최종적으로 교집합 요소를 포함하는 배열 res를 반환합니다.
- 결과 반환 :
- res 배열은 두 배열의 교집합 요소를 담고 있으며, 이 배열을 반환합니다.
시간 복잡도
- O(n + m) :
- n은 배열 nums1의 길이이고, m은 배열 nums2의 길이입니다.
- nums1의 모든 요소를 HashSet에 추가하는데 O(n)의 시간이 필요합니다.
- nums2를 순회하며 set에서 포함 여부를 확인하는 데 O(m)의 시간이 필요합니다.
- 따라서 전체 시간 복잡도는 O(n + m)입니다.
공간 복잡도
- O(n + m) :
- set과 intersec이라는 두 개의 HashSet을 사용합니다.
- set은 nums1의 요소를 저장하며, intersec은 두 배열의 교집합을 저장합니다.
- 각각 최대 O(n) 및 O(m)의 공간을 사용할 수 있으므로, 최악의 경우 공간 복잡도는 O(n + m)입니다.
