순열과 조합

순열과 조합

내 풀이

const consonant = ["ㄱ", "ㄴ", "ㄷ", "ㄹ"];

const count = 3;

function combination(consonant, count) {
  const hash = {};
  function recur(arr, result) {
    if (result.length == count) {
      result = result.sort().join("");
      if (!hash.hasOwnProperty(result)) {
        hash[result] = true;
      }
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      const copyOfArr = arr.slice();
      const copyOfResult = result.slice();
      const target = copyOfArr.splice(i, 1);
      copyOfResult.push(...target);
      recur(copyOfArr, copyOfResult);
    }
  }
  recur(consonant, []);

  return Object.keys(hash);
}

• 매번 arr와 result를 복사해줘야 하기 때문에 공간 복잡도가 크게 나올 것

• 조합보다는 순열에 적합한 풀이

답지 반영한 새 풀이

const consonant = ["ㄱ", "ㄴ", "ㄷ", "ㄹ"];

const count = 3;

function combination(consonant, count) {
  const list = [];
  function recur(prefix, arr) {
    for (let i = 0; i < arr.length; i++) {
      if ((prefix + arr[i]).length == count) {
        list.push(prefix + arr[i]);
        continue;
      }
      debugger;
      recur(prefix + arr[i], arr.slice(i + 1));
    }
  }
  recur("", consonant);
  return list;
}

• 순회 회수도 훨씬 줄어들고 공간 복잡도도 개선되었다.