06_[순열] 새로운 치킨 소스 레시피

문제

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

1. N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.
2. 재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다.
   1. 단, 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다.
3. 재료의 순서에 따라 맛이 달라지기 때문에, 재료를 넣는 순서가 다르다면 다른 레시피이다.

이 소문을 참고하여 '비밀의 승승장구 치킨 소스'가 될 수 있는 경우의 수를 모두 반환하는 함수를 작성하세요.

 

function combination(arr, selectNum) {

  const result = [];

  // num이 1일때는 각 요소를 이중 배열로 만듬

  // [1, 10, 1100, 1111]   =>   [[1],[10],[1100],[1111]]

  if (selectNum === 1) return arr.map((v) => [v]);

 

  arr.forEach((v, idx, arr) => {

    // v = 현재 값

    const fixed = v;

    // 인덱스를 제외한 값을 배열로 만든다.

    // > Array [10, 1100, 1111]

    // > Array [1, 1100, 1111]

    // > Array [1, 10, 1111]

    // > Array [1, 10, 1100]

    const restArr = arr.filter((_, index) => index !== idx);

    // > Array [Array [10], Array [1100], Array [1111]] => [[10],[1100],[1111]]

    // > Array [Array [1], Array [1100], Array [1111]]

    // > Array [Array [1], Array [10], Array [1111]]

    // > Array [Array [1], Array [10], Array [1100]]

    const combinationArr = combination(restArr, selectNum - 1);

    // > Array [Array [1, 10], Array [1, 1100], Array [1, 1111]] => [[1,10],[1,1100],[1,1111]]

    // > Array [Array [10, 1], Array [10, 1100], Array [10, 1111]]

    // > Array [Array [1100, 1], Array [1100, 10], Array [1100, 1111]]

    // > Array [Array [1111, 1], Array [1111, 10], Array [1111, 1100]]

    const combineFix = combinationArr.map((v) => [fixed, ...v]);

    result.push(...combineFix);

  });

  return result;

}

 

function newChickenRecipe(stuffArr, choiceNum) {

  // 상한 재료를 필터링 해주는 함수

  // slice의 -3을 하는 이유는 10000의 -3번째부터 가져와서 filtering 해줘야하기 때문

  let filtered = stuffArr.filter((elem) => String(elem).slice(-3) !== '000')

  

  return combination(filtered, choiceNum)

}

 

// > Array [Array [10, 1]]

// > Array [Array [1, 10]]

// > Array [Array [10000, 10, 1], Array [10000, 1, 10]]

// > Array [Array [10000, 1]]

// > Array [Array [1, 10000]]

// > Array [Array [10, 10000, 1], Array [10, 1, 10000]]

// > Array [Array [10000, 10]]

// > Array [Array [10, 10000]]

// > Array [Array [1, 10000, 10], Array [1, 10, 10000]]