- 문제:
하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴
입출력 예시:
let output1 = powerSet('abc');
console.log(output1); // ['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']
let output2 = powerSet('jjump');
console.log(output2); // ['', 'j', 'jm', 'jmp', 'jmpu', 'jmu', 'jp', 'jpu', 'ju', 'm', 'mp', 'mpu', 'mu', 'p', 'pu', 'u']풀이:
(주의) 입출력 예시를 통해 알 수 있듯이, 중복되는 요소의 값은 제외가 되고 결과값의 알파벳순으로 정렬되어야 한다.
DFS를 활용해야 한다는 것까지 생각해 냈지만, 코드로 구현해내지 못했다.
reference code를 보고 싶지 않았다.
1시간 동안 혼자서 끙끙댔고, 다시 1시간 동안 검색 등을 해보았지만 해결되지 않았다.
결국, reference code를 보았다. 그럼에도 이해가 되지 않았다.🧐
30분동안 DFS에 집중해 풀어보았다. 잊지 말자는 심정으로 글을 남긴드아.
이 문제의 핵심은 이진 탐색 트리처럼 DFS(깊이 우선 탐색)을 해야 한다는 것이다.
왜냐하면 우리는 부분 집합의 배열을 반환해야 하기 때문이다.
부분 집합
[1, 2, 3]의 부분 집합은 아래 처럼 구할 수 있다.
- 요소 없이 구성된 집합(공집합) []
- 요소 하나로 구성된 집합 [1][2] [3]
- 요소 두개로 구성된 집합 [1, 2][1, 3] [2, 3]
- 요소 세개로 구성된 집합 [1, 2, 3]
이러한 부분 집합은 Tree 구조로 표현해 볼 수 있다.(직접 그렸는데..)
왼쪽에는 ''(빈값이)을 넣고 오른쪽에는 각 level에 해당하는 인자 각 요소를 붙여 준다.
계속 재귀를 사용하여 DFS 한다. 마지막 level에 왔을 때 (요소의 총 길이) 위에서 붙여준 결과값을 결과로 반환할 배열에 넣어준다. 마지막에 sort()하여 정렬한다.
const powerSet = function (str) {
// 문자열로 들어온 인자를 배열로 만들어, 정렬한다.
let arr = str.split('').sort();
// 반복 요소를 삭제해 준다.
const uniArr = arr.filter((item, index) => arr.indexOf(item) === index);
let subSets = [];
function pickOrNot(i, subset) {
// base case (탈출 조건)
if (i === uniArr.length) {
subSets.push(subset)
return; // 식을 마무리 진다.
}
// 재귀의 시작에 요소는 빈 문자열로 한다
// 위 그림에서 왼쪽 정점에 해당하는 재귀이다. '' 문자열이 각 level의 왼쪽 정점에 들어간다.
pickOrNot(i+1, subset);
// 위 그림에서 오른쪽 정점에 해당하는 재귀이다.
pickOrNot(i+1, subset+uniArr[i]);
// 순서는...
// []과 [3]이 가장 먼저 subSets에 들어간다. 왼쪽 정점에 들어가는 재귀가 먼저 시작하기 때문이다.
}
pickOrNot(0, '');
return subSets.sort();
}부분 집합에 대하 이해가 필요했다.
Tree 구조,이진탐색,DFS세 가지를 정확히 이해하고 있었다 구현할 수 있다.
DFS라고 해서 무조건 stack을 사용하지 않아도 되는 점을 배웠다.이진 탐색과DFS의 조합을 공부할 수 있었다.재귀의 활용이 무궁무진하다.
Log