[Toy] powerSet

George·2022년 4월 14일

Immersive Toy Problem

문제

목록 보기

7/14

11_powerSet

문제 🙋

하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다.

입력 🔜

인자 1 : str

string 타입의 공백이 없는 알파벳 소문자 문자열

출력 🔚

배열(arr)을 리턴해야 합니다.
arr[i]는 각 부분집합의 원소로 구성된 문자열

주의사항 ⚠️

arr[i]는 각 부분집합을 구성하는 원소를 연결한 문자열입니다.
arr[i]는 알파벳 순서로 정렬되어야 합니다.
집합은 중복된 원소를 허용하지 않습니다.
부분집합은 빈 문자열을 포함합니다.
arr은 사전식 순서(lexical order)로 정렬되어야 합니다.

입출력 예시 ⌨️

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']

Pseudo Code ✍️

1. 문자열을 배열로 만들기. split('')
2. 알파벳 순으로 나열해야 하기 때문에 sort()사용
3. 중복을 제거해야 한다. forEach()사용
4. 연속되는 for문을 사용해도 두자리, 세자리, 네자리 문자열을 만들기 어렵다.
5. Reference code를 보며 참고하자.

Code 💻

const powerSet = function (str) {
 // TODO: 여기에 코드를 작성합니다.
  // 배열 만들기, 알파벳 정렬
 const sorted = str.split('').sort();
  // 중복 제거
  const deduplicated = []
  sorted.forEach((el) => {
    if(!deduplicated.includes(el)){
      deduplicated.push(el);
    }
  })
  // 요소들을 넣어줄 배열 및 함수 생성
  let subSets = [];
  const pickOrNot = (idx, subset) => {
    // base case
    if (idx === deduplicated.length) {
      // 마지막 문자까지 검토한 경우
      subSets.push(subset);
      return;
    }
    // recursive case
    // idx번째 문자가 포함되지 않는 경우
    pickOrNot(idx + 1, subset);
    // idx번째 문자가 포함되는 경우
    pickOrNot(idx + 1, subset + deduplicated[idx]);
  };
  // 함수실행(''은 포함, 0부터 시작하기 때문에 인자로 아래와 같이 삽입)
  pickOrNot(0, '');
  // 결과 배열을 다시한번 알파벳 순으로 배열
  return subSets.sort();
};