[JS]_daily coding #33

[SEB FE] Section3 Daily Coding 15_powerSet

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

주의사항

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

수도 코드

1. 입력받은 문자열의 중복을 제거하고, 정렬한다. arr
2. 부분집합을 구해서 저장할 배열을 선언하고, 초기값으로 빈문자열을 넣는다.
3. arr 배열의 요소를 하나씩 순회하면서
4. 부분집합 배열의 원소와 조합한 문자열을 부분집합 배열에 추가한다.
5. 부분집합 배열을 반환한다.

• 위의 'abc'의 부분 집합을 구한다면 아래와 같다.
  초기 배열 -['']
  i=0 - ['', 'a']
  i=1 - ['','a', 'ab', 'b']
  i=2 - ['', 'a', 'ab', 'b', 'ac' 'bc' 'abc']

문제의 조건에서 사전식 순서로 정렬되어야한다고 했기 때문에 마지막에 부분집합 배열을 정렬해서 반환한다.

코드

const powerSet = function (str) {
  const arr = Array.from(new Set(str)).sort()

  let set = [""]; 
  for (let i = 0; i < arr.length; i++) { 
    let len = set.length;
    for (let j = 0; j < len; j++) {
      set.push(set[j] + arr[i]);
    }
  }
  return set.sort();
};

레퍼런스 코드

레퍼런스 코드에서는 재귀를 사용해서 풀었다.

const powerSet = function (str) {
  // 정렬
  const sorted = str.split('').sort();

  // 중복 제거
  const deduplicated = sorted.reduce((acc, item) => {
    if (acc[acc.length - 1] === item) {
      return acc;
    } else {
      return acc.concat(item);
    }
  });

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

  pickOrNot(0, '');

  return subSets.sort();
};