TIL. 새로운 치킨 소스 레시피

- 문제:

개업 이래로 항상 승승장구하는 '승승장구 치킨집'의 비결은 소스에 있다. 수많은 타사 브랜드 치킨집들이 승승장구 치킨집의 소스 비결을 알아내려고 했으나 빈번히 포기했다.
그 이유는 5대째 내려오는 '비밀의 승승장구 치킨 소스 비율 레시피'는 70억 인구 중 사장님만 알고 있기 때문이다. 최근, 누리꾼 사이에서 이 레시피의 일부분을 발췌했다는 소문을 듣게 되었다.
그 소문은 다음과 같다.

N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.
재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다.
단, 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다.
재료의 순서에 따라 맛이 달라지기 때문에, 재료를 넣는 순서가 다르다면 다른 레시피이다.
이 소문을 참고하여 '비밀의 승승장구 치킨 소스'가 될 수 있는 경우의 수를 모두 반환하는 함수를 작성하세요.

- 입출력예시:

const output1 = newChickenRecipe([1, 10, 1100, 1111], 2);
console.log(output1);
/*
  [
    [1, 10], [1, 1100], [1, 1111],
    [10, 1], [10, 1100], [10, 1111],
    [1100, 1], [1100, 10], [1100, 1111],
    [1111, 1], [1111, 10], [1111, 1100]
  ];
*/

const output2 = newChickenRecipe([10000, 10, 1], 3);
console.log(output2); // []

const output3 = newChickenRecipe([11, 1, 10, 1111111111, 10000], 4);
console.log(output3);
/* 
  [
    [1, 10, 11, 1111111111],
    [1, 10, 1111111111, 11],
    [1, 11, 10, 1111111111],
    [1, 11, 1111111111, 10],
    [1, 1111111111, 10, 11],
    [1, 1111111111, 11, 10],
    [10, 1, 11, 1111111111],
    [10, 1, 1111111111, 11],
    [10, 11, 1, 1111111111],
    [10, 11, 1111111111, 1],
    [10, 1111111111, 1, 11],
    [10, 1111111111, 11, 1],
    [11, 1, 10, 1111111111],
    [11, 1, 1111111111, 10],
    [11, 10, 1, 1111111111],
    [11, 10, 1111111111, 1],
    [11, 1111111111, 1, 10],
    [11, 1111111111, 10, 1],
    [1111111111, 1, 10, 11],
    [1111111111, 1, 11, 10],
    [1111111111, 10, 1, 11],
    [1111111111, 10, 11, 1],
    [1111111111, 11, 1, 10],
    [1111111111, 11, 10, 1],
  ]
*/

- 풀이;

function newChickenRecipe(stuffArr, choiceNum) {
  
  // 먼저 0이 3개 미만인 재료만 따로 배열로 만들자.
  let freshArr = [];

  for (let i = 0; i < stuffArr.length; i++) {
    const element = String(stuffArr[i])
      .split('')
      .filter((e) => e === '0');
    if (element.length <= 2) {
      freshArr.push(stuffArr[i]);
    }
  }  
  
  // 수열은 순서를 고려하면서 뽑는다.
  // [1, 2, 3, 4]에서 3가지 수를 뽑는 경우를 반환한다고 했을 때,
  // [2, 3, 4]에서 2가지 수를 뽑는 경우에 1을 추가하고, [1, 3, 4]에서 2가지 수를 뽑는 경우에 2를 추가하는 등
  // 재귀를 활용하여 문제를 해결할 수 있다.

  let result = [];
  
  // 탈출 조건은 선택하고자 하는 수의 크기가 1이면, 전달인자의 배열의 모든 요소를 하나씨 나열하게 한다.
  // 전달인자의 배열의 길이에 상관없이 1개를 뽑는 경우는 각 요소를 배열로 구현할 수 있다.
  // [b, c, d]에서 1개를 뽑을 수 있는 경우는 [[b], [c], [d]] 이렇게 3가지 이다.
  if (choiceNum === 1) return freshArr.map((item) => [item]);
  
  // forEach에서 활용 가능한 전달 인자를 모두 사용한다.
  freshArr.forEach((value, index, origin) => {
    // value를 제외한 나머지를 구해보자 
    // (나머지의 숫자-1 만큼 뽑는 경우를 각 value에 더해주면, 그게 result이다)
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)];
    
    // 재귀를 해주고 (위에서 말한 것 처럼)
    const permutations = newChickenRecipe(rest, choiceNum - 1);
    
    // 그 배열의 모든 요소를 현재 value에서 붙여준다
    const attach = permutations.map((el) => [value, ...el]);
    result.push(...attach); 
  })
  return result;
}

- ref:

function newChickenRecipe(stuffArr, choiceNum) {
  // stuffArr에서 0이 3개 이상이라면 전부 필터로 거르기.
  let freshArr = [];

  for (let i = 0; i < stuffArr.length; i++) {
    const element = String(stuffArr[i])
      .split('')
      .filter((e) => e === '0');
    if (element.length <= 2) {
      freshArr.push(stuffArr[i]);
    }
  }

  // 정렬
  freshArr.sort((a, b) => a - b);

  // 엣지 케이스 처리
  if (freshArr.length === 0 || freshArr.length < choiceNum) return [];

  // 레시피 초기화
  let result = [];

  // freshArr를 상대로 순열 구하기
  const permutation = (arr, bucket, n) => {
    if (n === 0) {
      result.push(bucket);
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      // 하나를 초이스함
      const choice = arr[i];
      // 배열을 슬라이스함
      const sliceArr = arr.slice();
      // 초이스만 뺀다
      sliceArr.splice(i, 1);
      // 재귀
      permutation(sliceArr, bucket.concat(choice), n - 1);
    }
  };

  // 실행
  permutation(freshArr, [], choiceNum);
  
  // 순열의 길이 반환
  return result;
}