Algorithm problem-11

1. 문제

• 문자열로 구성할 수 있는 모든 부분집합을 담아 배열로 리턴
• 사전식 정렬해서 리턴

2. 시도

• 우선은 받은 문자열이 중복되지 않게 분리를 하자
• 분리한 문자열을 한개씩 빈 배열에 넣고, 두개부터 문자열의 길이까지 붙여보면서 결과를 담은 배열 내에 중복되지 않으면 푸쉬해서 넣어보자
• 생각보다 2개 이상의 문자열을 만든다는 개념을 짜는게 어려웠다
• 결국은 실패, 빈 스트링이 끼거나 'aba'등 원하지 않던 문자열까지 생성되어 실패

3. 수도코드

const powerSet = function (str) {
  // str중 중복되지 않게 나열
  let chr = [];
  for (let i = 0; i < str.length; i++) {
    if (!chr.includes(str[i])) {
      chr.push(str[i])
      chr.sort();
    }
  }
  console.log(chr)
  // 중복되지 않게 2개 이상의 글자로 만들자
  let word = [];
  let abc = ''
  for (let i = 0; i < chr.length; i++) {
    for (let j = 1; j < chr.length; j++) {
      if (chr[i] !== chr[j]) {
        abc = abc + chr[i]
      }
      word.push(abc)
      abc = ''
    }
    console.log(word)
  }
  function makeWord(chr) {
    for (let i = 0; i < chr.length; i++) {
      if (chr !== chr[i]) {
        chr = chr + chr[i]
      }
      word.push(chr)
    }
  }
  for (let i = 0; i < chr.length; i++) {
    makeWord(chr)
  }
  console.log(word)
  let result = [];
  for (let i = 0; i < str.length - 1; i++) {
    for (let j = 1; j < str.length; j++) {
      if (str[i] !== str[j] && !result.includes(str[i] + str[j])) {
        result.push(str[i] + str[j])
        result.sort();
      }
    }
  }
  console.log(result)
};

4. 레퍼런스

const powerSet = function (str) {
  let chr = []; // str중 중복되지 않게 나열
  for (let i = 0; i < str.length; i++) {
    if (!chr.includes(str[i])) {
      chr.push(str[i])
      chr.sort(); } }
  let max = '' // chr을 합쳐서 견본으로 사용
  for (let i = 0; i < chr.length; i++) {
    max = max + chr[i] }
  // 견본을 한절씩 잘라서 부분집합인 단어를 만들어 결과에 담는다
  let result = [];
  // 견본에서 부분집합을 만들어 낼 내부 함수를 구현
  const filter = function (idx, cur) {
    // base case, 인덱스와 견본의 길이가 같을 때에 푸쉬하고 종료
    if (idx === max.length) {
      result.push(cur)
      return }
    // recursive case
    // idx를 +1씩 해줌으로 빈 문자열을 넣을 수 있게 됨
    filter(idx + 1, cur);
    // cur에 max[idx]를 해줘서 한 절씩 늘려가며 넣을 수 있게 됨
    filter(idx + 1, cur + max[idx]) }
  filter(0, ''); // 재귀의 시작은 0번과 빈문자열
  return result.sort()
};