두 개의 배열을 인자로 받아, 한 배열이 다른 배열의 부분 집합인지 판별하는 JavaScript 함수를 작성해야 합니다. 단순히 값의 존재 여부만 확인해서는 안 되며, 다음 조건을 모두 만족해야 합니다.
첫 번째 배열(arr1)의 모든 값은 두 번째 배열(arr2)에 반드시 존재해야 합니다.
arr1에 중복된 값이 있다면, arr2에도 동일한 횟수만큼 중복되어 있어야 합니다.
예를 들어 arr1 = ['a', 'a']이고 arr2 = ['b', 'a']라고 가정해 보겠습니다. 'a'는 첫 번째 배열에 두 번 등장하지만 두 번째 배열에는 한 번만 등장하므로, 이 경우 결과는 false가 됩니다.
접근 방식: 해시 기반 빈도 계산
값의 존재 여부만 확인하는 includes()나 Set을 활용한 방법은 중복 개수까지는 검증하지 못합니다. 따라서 각 값이 몇 번 등장했는지를 추적하는 빈도 맵(frequency map)을 사용하는 것이 정확한 해결책입니다.
먼저 두 번째 배열(arr2)의 각 값별 등장 횟수를 객체에 저장합니다.
첫 번째 배열(arr1)을 순회하면서 각 값이 빈도 맵에 아직 남아 있는지 확인합니다. 없다면 즉시 false를 반환합니다.
값이 존재하면 해당 개수를 1씩 차감하여 중복 요구 사항까지 처리합니다.
모든 값을 통과하면 true를 반환합니다.
코드 구현
const isSubset = (arr1, arr2) => {
// arr2의 요소별 개수를 저장할 빈도 맵 생성
const freq = {};
for (const value of arr2) {
freq[value] = (freq[value] || 0) + 1;
}
// arr1의 값을 하나씩 확인하며 소비
for (const value of arr1) {
if (!freq[value]) {
return false; // 값이 없거나 개수가 부족한 경우
}
freq[value]--;
}
return true;
};
console.log(isSubset(['B', 'A', 'C', 'A'], ['A', 'B', 'C', 'A']));
console.log(isSubset(['B', 'A', 'C', 'A'], ['A', 'B', 'C', 'D']));
console.log(isSubset(['a', 'a'], ['b', 'a']));
실행 결과
true false false
결과 분석
첫 번째 호출: arr1과 arr2가 'A' 2개, 'B' 1개, 'C' 1개로 완전히 일치하므로 true입니다.
두 번째 호출: arr1에는 'A'가 두 번 필요하지만 arr2에는 한 번만 있고, 대신 불필요한 'D'가 포함되어 있으므로 false입니다.
세 번째 호출: 앞서 살펴본 예시처럼 'a'의 등장 횟수가 맞지 않아 false입니다.
시간 및 공간 복잡도
이 방식은 두 배열을 각각 한 번씩만 순회하므로 시간 복잡도는 O(n + m)입니다(n, m은 각 배열의 길이). 또한 빈도 맵에는 최대 m개의 키만 저장되므로 공간 복잡도 역시 O(m)으로 효율적입니다. 덕분에 배열의 길이가 커져도 성능 저하 없이 부분 집합 여부를 빠르게 판별할 수 있습니다.