알고리즘 문제풀이 2

Power Set 문제

recursion 활용 문제
가위바위보 문제의 변형이라고 생각하고 풀어보자.
가위바위보의 경우, 중복 허용 but 해당 문제는 중복 허용X

/*
 * 주어진 문자열의 '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"]
 */

solution 1

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;
};

solution 2

recursion 미사용. but 간략. 시간복잡도 파악하기 가장 용이

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;
};

solution 3

효율적인 코드인것 같긴 하나, 이해가 되지 않는다...(페어분의 솔루션임)

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();
};

그리고 나의 코드

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;
};