문제 정의
리터럴 값으로 이루어진 배열을 첫 번째이자 유일한 인수로 받아, 원본 배열의 요소로 만들 수 있는 모든 가능한 하위 배열(부분 집합)을 담은 배열을 생성해 반환하는 JavaScript 함수를 작성해야 합니다.
예를 들어 입력 배열이 다음과 같다면,
const arr = [1, 2, 3];
출력은 다음과 같아야 합니다.
const output = [
[2],
[1],
[3],
[1,2,3],
[2,3],
[1,2],
[1, 3],
[]
];
참고로 하위 배열이 출력되는 순서는 결과에 영향을 주지 않으므로 크게 중요하지 않습니다.
접근 방법
이 문제는 재귀 호출 없이 반복문만으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 초기화: 결과 배열을 빈 부분 집합 하나만 담은 상태(
[[]])로 시작합니다. 빈 배열 역시 유효한 부분 집합입니다. - 정렬: 배열을 먼저 오름차순으로 정렬해 중복된 요소들이 서로 인접하도록 만듭니다.
- 확장: 각 요소를 순회하면서 지금까지 만든 모든 부분 집합의 복사본에 해당 요소를 추가해 새로운 부분 집합을 생성합니다.
- 중복 처리: 연속해서 나타나는 동일한 요소의 개수를 세어(count), 각 기존 부분 집합에 그 요소를 1개부터 count개까지 추가한 경우만 만들도록 함으로써 중복 부분 집합이 생기지 않게 합니다.
고유한 요소가 n개인 배열의 부분 집합 개수는 2ⁿ개이므로, 이 알고리즘의 시간 복잡도는 O(n × 2ⁿ)입니다.
구현 코드
const arr = [1, 2, 3];
const findAllSubsets = (arr = []) => {
arr.sort();
const res = [[]];
let count, subRes, preLength;
for (let i = 0; i < arr.length; i++) {
count = 1;
while (arr[i + 1] && arr[i + 1] == arr[i]) {
count += 1;
i++;
}
preLength = res.length;
for (let j = 0; j < preLength; j++) {
subRes = res[j].slice();
for (let x = 1; x <= count; x++) {
if (x > 0) subRes.push(arr[i]);
res.push(subRes.slice());
}
}
};
return res;
};
console.log(findAllSubsets(arr));
실행 결과
콘솔에는 다음과 같이 출력됩니다.
[
[], [ 1 ],
[ 2 ], [ 1, 2 ],
[ 3 ], [ 1, 3 ],
[ 2, 3 ], [ 1, 2, 3 ]
]
코드 동작 단계별 설명
arr.sort()로 배열을 정렬해 중복 요소를 서로 인접하게 배치합니다.res를[[]]로 초기화해 빈 부분 집합에서 출발합니다.- 바깥쪽
for루프가 각 요소를 순회하고, 내부while루프가 연속된 동일 요소의 개수를 셉니다. preLength에 현재까지의 부분 집합 개수를 저장한 뒤, 각 기존 부분 집합을slice()로 복사해 현재 요소를 추가한 새 부분 집합을res에 추가합니다.- 모든 요소를 처리하면 완성된 부분 집합 목록 전체를 반환합니다.
이 방식은 재귀 함수를 사용하지 않기 때문에 입력 배열이 커져도 call stack 오버플로우를 걱정할 필요 없이 안정적으로 동작한다는 장점이 있습니다.