두 개의 배열 A와 B가 주어졌을 때, 두 배열에 공통으로 존재하는 원소들, 즉 교집합을 찾는 문제입니다. 예를 들어 A = [1, 4, 5, 3, 6]이고 B = [2, 3, 5, 7, 9]라면, 두 배열 모두에 포함된 원소는 3과 5이므로 교집합은 [3, 5]가 됩니다.
해결 접근 방법
이 문제는 해시맵(딕셔너리)을 이용해 각 원소의 등장 횟수를 추적하면 효율적으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- 두 배열 A와 B를 입력받습니다.
- A의 길이가 B보다 작으면 두 배열을 서로 교환합니다. (더 긴 배열의 빈도수를 미리 계산하기 위함입니다.)
- 배열 A의 각 원소 빈도수를 계산하여 딕셔너리 m에 저장합니다.
- 배열 B의 각 원소 e에 대해, e가 m에 존재하고 해당 빈도수가 0이 아니라면:
- m[e]의 값을 1 감소시킵니다.
- 원소 e를 결과 배열에 추가합니다.
- 최종 결과 배열을 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
m = {}
if len(nums1) < len(nums2):
nums1, nums2 = nums2, nums1
for i in nums1:
if i not in m:
m[i] = 1
else:
m[i] += 1
result = []
for i in nums2:
if i in m and m[i]:
m[i] -= 1
result.append(i)
return result
ob1 = Solution()
print(ob1.intersect([1, 4, 5, 3, 6], [2, 3, 5, 7, 9]))입력
[1,4,5,3,6] [2,3,5,7,9]
출력
[3,5]
복잡도 분석
시간 복잡도: O(n + m) — 각 배열을 한 번씩 순회하며 딕셔너리 조회는 O(1)이기 때문입니다. 여기서 n과 m은 각각 두 배열의 길이입니다.
공간 복잡도: O(n) — 더 긴 배열의 원소 빈도수를 저장하는 딕셔너리가 필요합니다.
마무리
이 방식은 중복 원소를 올바르게 처리할 수 있다는 장점이 있습니다. 예를 들어 한 배열에 3이 두 번 등장하고 다른 배열에 한 번만 등장한다면, 결과에는 3이 한 번만 포함됩니다. 정렬 기반 투 포인터 방식(O(n log n))보다 해시맵을 활용한 이 방법이 일반적으로 더 효율적입니다.