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

새로운 치킨 소스 레시피

문제

개업 이래로 항상 승승장구하는 '승승장구 치킨집'의 비결은 소스에 있다. 수많은 타사 브랜드 치킨집들이 승승장구 치킨집의 소스 비결을 알아내려고 했으나 빈번히 포기했다.

그 이유는 5대째 내려오는 '비밀의 승승장구 치킨 소스 비율 레시피'는 70억 인구 중 사장님만 알고 있기 때문이다. 최근, 누리꾼 사이에서 이 레시피의 일부분을 발췌했다는 소문을 듣게 되었다.

그 소문은 다음과 같다.

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

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

입력

인자 1: stuffArr

• Number 타입의 재료를 담은 배열

인자 2: choiceNum

• Number 타입의 1 이상 stuffArr 길이 이하의 자연수
• 재료를 선택할 수 있는 수를 뜻합니다.
• ex) 2

출력

• Number 타입을 반환해야 합니다.

주의사항

• 만약, 주어진 재료 모두 사용할 수 없다면 빈 배열[]을 반환해야 합니다.
• 만약, 사용할 수 있는 재료가 choiceNum보다 작다면 빈 배열[] 을 반환해야 합니다.
• 조합 및 요소는 작은 숫자 -> 큰 숫자로 정렬합니다.

입출력 예시

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) {

  // 000으로 끝나는 재료를 걸러냄
  let freshArr = stuffArr.filter((el) => String(el).slice(-3) !== "000");

  // 가능한 모든 조합을 찾는 재귀 함수를 정의함
  const recur = function (arr, choiceNum) {
    let result = [];

    // 기저 조건: choiceNum이 1인 경우, 각 요소를 1D 배열로 변환하여 리턴함
    if (choiceNum === 1) return arr.map((hand) => [hand]);

    // 재귀적인 경우: 배열의 각 요소에 대해 반복함
    arr.forEach((hand, idx, arr) => {
      const fixer = hand; // 현재 요소를 "fixer"로 저장함
      const restArr = arr.filter((_, index) => index !== idx); // 현재 요소를 제외한 새로운 배열을 만듦
      const permuationArr = recur(restArr, choiceNum - 1); // 새로운 배열에서 (choiceNum - 1) 요소로 가능한 모든 조합을 재귀적으로 찾음
      const combineFixer = permuationArr.map((hand) => [fixer, ...hand]); // permuationArr의 각 조합에 "fixer"를 앞에 추가함
      result.push(...combineFixer); // 결과 조합을 "result" 배열에 추가함
    });

    return result;
  };

  // recur 함수를 호출하여 가능한 모든 조합을 찾음
  return recur(freshArr, choiceNum);
}

forEach 구문은 배열 arr을 반복하면서 다음 작업을 수행합니다:

1. 현재 요소를 hand 변수에 저장합니다.
2. 현재 요소를 제외한 나머지 요소로 새 배열 restArr를 만듭니다.
3. recur 함수를 재귀적으로 호출하여 새 배열 restArr에서 (choiceNum - 1)개의 요소를 선택한 모든 가능한 조합을 찾습니다.
4. permuationArr의 각 조합 앞에 fixer 요소를 추가하여 새로운 배열 combineFixer를 만듭니다.
5. combineFixer 배열을 result 배열에 추가합니다.

이러한 방식으로, recur 함수는 입력 배열에서 choiceNum 개의 요소로 가능한 모든 조합을 찾게 됩니다.

레퍼런스 코드

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