문제 상황
두 개의 배열 arr1과 arr2를 각각 첫 번째, 두 번째 인자로 받아 두 배열의 교집합(공통 요소)을 구하는 JavaScript 함수를 작성해야 합니다. 여기서 중요한 조건은, 특정 요소가 양쪽 배열에 여러 번 등장한다면 결과 배열에도 그 등장 횟수만큼 중복해서 포함해야 한다는 점입니다.
예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
const arr1 = [2, 7, 4, 6, 7, 4]; const arr2 = [7, 1, 9, 7, 4, 5];
숫자 7은 두 배열 모두에서 두 번씩 등장하고, 숫자 4는 arr1에 두 번, arr2에 한 번 등장합니다. 따라서 기대되는 출력은 다음과 같습니다.
const output = [7, 7, 4];
해결 코드
이 문제는 해시 객체(맵)를 활용해 각 요소의 등장 횟수를 추적하는 방식으로 깔끔하게 해결할 수 있습니다.
const arr1 = [2, 7, 4, 6, 7, 4];
const arr2 = [7, 1, 9, 7, 4, 5];
const intersect = (arr1 = [], arr2 = []) => {
const map = {};
arr1.forEach(a => {
map[a] = map[a] ? map[a] + 1 : 1;
})
const result = [];
for(let key of arr2) {
if(key in map && map[key] > 0) {
result.push(key);
map[key]--;
}
}
return result;
};
console.log(intersect(arr1, arr2));코드 동작 원리
위 코드의 핵심 로직은 다음 세 단계로 요약할 수 있습니다.
빈도 카운트 생성: 첫 번째 배열(arr1)을 순회하면서 각 숫자가 몇 번 등장하는지 객체(map)에 기록합니다.
교집합 판별: 두 번째 배열(arr2)을 순회하면서 해당 요소가 map에 존재하고, 아직 사용 가능한 개수(map 값)가 0보다 큰지 확인합니다.
결과 추가 및 차감: 조건을 만족하면 결과 배열에 요소를 push하고, map의 해당 값을 1 감소시켜 동일한 요소가 실제 등장 횟수를 초과하여 포함되지 않도록 합니다.
실행 결과
콘솔에는 다음과 같이 출력됩니다.
[7, 7, 4]
성능 참고 사항
이 알고리즘은 해시 객체를 활용하기 때문에 시간 복잡도는 O(n + m)입니다(n, m은 각 배열의 길이). 배열마다 중첩 반복문을 돌며 비교하는 O(n × m) 방식보다 훨씬 효율적이므로, 배열의 크기가 클 때도 안정적인 성능을 기대할 수 있습니다.