728x90
Power Set 문제
recursion 활용 문제
가위바위보 문제의 변형이라고 생각하고 풀어보자.
가위바위보의 경우, 중복 허용 but 해당 문제는 중복 허용X
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/*
* 주어진 문자열의 'power set'으로 이루어진 배열을 return하는 함수를 작성하세요.
*
* power set이란?
* 비어있는 집합을 포함한 모든 부분집합(subset)의 모음.
*
* 예시 :
*
* powerSet("abc")
* -> [ '' , 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc' ]
*
* 참고 :
* 1. 모든 부분집합의 문자들은 알파벳 순서로 정렬되어야 합니다.
* 2. 같은 문자로 이루어진 부분집합은 순서와 무관하게 하나로 인식합니다. ('ab'와 'ba'는 같습니다.)
*
* 예시 2 :
*
* powerSet("jump")
* -> ["", "j", "ju", "jm", "jp", "jmu", "jmp", "jpu", "jmpu", "u", "m", "p", "mu", "mp", "pu", "mpu"]
*/
|
cs |
solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
const powerSet = function (str) {
let result = [""]; //빈문자열은 미리 집어넣어놓기
let subset = "";
let check = {};
function makeSubset() {
//기저조건: 문자열에 있는 알파벳 모두 다 넣었을 때
if (subset.length >= str.length) {
return;
}
for (let i = 0; i < str.length; i++) {
if (!check[str[i]]) {
//1. 아직 subset에 안들어간 알파벳이면
//str[i]가 한글자씩 들어감
subset += str[i]; //2. 합치고
check[str[i]] = true;
//3. str[i]가 들어갔다고 표시해줘서 중복을 방지
let sortSubset = subset.split("").sort().join("");
// => 모든 부분집합의 문자들은 알파벳 순서로 정렬되어야 합니다.
if (result.indexOf(sortSubset) === -1) {
//3은 jjum 와 같은 알파벳 중복을 막아 준 것이고 이 코드는 jmup와 jpum 같은 중복을 없애기 위한 것이다.
result.push(sortSubset);
}
makeSubset(); //4. 재귀 들어가서 그 뒤에 알파벳 덧붙이고
subset = subset.slice(0, -1);
//5-1. 재귀 빠져나오면 즉 기저조건에서 나오게 되면, 현재 subset은 "jump"이고 i = 4이다.
//그리고 해당 코드를 통해 subset은 jum으로 바뀐다.
//즉 순서대로 넣어주고 다시 뒤로 돌아가서 처음부터 중복제거해서 넣어주는 걸 반복한다고 생각하면 된다.
check[str[i]] = false;
//3번 부분을 다시 초기화.
}
}
}
makeSubset();
return result;
};
|
cs |
solution 2
recursion 미사용. but 간략. 시간복잡도 파악하기 가장 용이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
const powerSet = function (str) {
let strArr = str.split(""); //문자열을 배열로 쪼개준다.
let arr = [];
for (let i = 0; i < strArr.length; i++) {
if (!arr.includes(strArr[i])) {
arr.push(strArr[i]);
}
} // 우선 한글자씩 넣어준다.
//=> 해당코드 불필요하다고 생각했는데, 한글자씩 넣어줄때 중복 제거해서 넣어주는 작업이었다.
//arr = ["j","u","m","p"]
let result = [""]; //최종 결과값
for (let i = 0; i < arr.length; i++) { //한글자씩 넣어준 arr를 순회한다.
let len = result.length;
for (let x = 0; x < len; x++) {
result.push(result[x] + arr[i]);
}
}
return result;
};
|
cs |
solution 3
효율적인 코드인것 같긴 하나, 이해가 되지 않는다...(페어분의 솔루션임)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
const powerSet = function (str) {
// 멱집합 : 2^(str.length) 개 만큼 존재한다.
// 최초의 원소부터, 최초의 원소를 포함하는 부분집합은 2^(str.length-1)개 존재함
// 그 다음의 원소는, 2^(str.length-2)개 존재함
let splittedStr = Array.from(new Set(str.split("")));
// new Set : 중복 제거하기
// Array.from : 배열 형태로 복사하기
//즉 주어진 문자열에서 중복 제거하고 문자열의 문자 하나씩으로 이루어진 새로운 배열 만들기
let answer = [];
function recursion(arr, depth) {
if (depth === splittedStr.length) {
answer.push(arr.slice().sort().join(""));
// .slice() : 똑같이 생긴 배열을 복사해서 사용하기.
// answer.push(JSON.parse(JSON.stringify(arr))); : 이 방법을 썼다가, 위에 slice로 바꿈.
return;
} else {
arr[depth] = splittedStr[depth];
recursion(arr, depth + 1);
arr[depth] = undefined;
recursion(arr, depth + 1);
}
}
recursion([], 0);
return answer.sort();
};
|
cs |
그리고 나의 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | const sortSet = function (set) { return set.split("").sort().join(""); }; //결국 테스트 파일의 sortSet 메소드를 활용했다 ㅠ const powerSet = function (str) { let newStr = str.split(""); let count = newStr.length; let allRes = []; //최종 결과값 allRes.push(""); let subset = function (number) { if (number === 0) { newStr.forEach((elem) => { allRes.push(elem); }); //여기서 중복제거하고 하나씩 넣어주는 코드가 있으면 좋을듯 } if (number > 0) { allRes.forEach((elem) => { if (elem.length === number) { newStr.forEach((string) => { let elemArr = elem.split(""); if (elemArr.indexOf(string) === -1) { let newElem = sortSet(elem + string); if (allRes.indexOf(newElem) === -1) { allRes.push(sortSet(newElem)); } } }); } }); } number = number + 1; if (number === count) { return; } subset(number); }; subset(0); return allRes; }; | cs |
728x90
'CS STUDY > Algorithm&Data structure' 카테고리의 다른 글
[JS]알고리즘 문제풀이5_bind( )함수 (0) | 2020.11.06 |
---|---|
[JS]알고리즘 문제풀이4_재귀활용 (0) | 2020.11.06 |
[JS]알고리즘 문제풀이2_재귀활용 (0) | 2020.11.05 |
[JS]알고리즘 문제풀이1_해시테이블 활용 (0) | 2020.11.03 |
해시테이블(HashTable)과 해시함수(HashFunction)에 대해서 (0) | 2020.11.02 |