Algorithm problem-순열

1. 문제

• 유명한 치킨집의 레시피 일부를 구하여, 그것을 바탕으로 치킨 소스 레시피를 개발
• 주어진 재료는 1로 시작하고 0과 1로만 이루어진 암호코드로 되어 있음
• 0이 3개 이상인 재료는 상한 재료이므로 제외하여아 한다
• 재료가 부족하여 레시피를 만들 수 없는 경우에는 빈 배열을 리턴
• 주어진 재료 N개 중 M개만을 사용하여 조합하는 모든 경우의 수를 리턴

2. 시도

• 주어진 재료 중 상한 재료를 제외하고 신선한 재료 배열을 만든다
• 신선한 재료 배열이 골라야 할 재료의 개수보다 작으면 레시피를 만들수 없으므로 빈 배열 리턴
• 생각보다 어려워 레퍼런스를 보고 풀었다

3. 수도코드

function newChickenRecipe(stuffArr, choiceNum) {
  // 신선한 재료만 담아줄 배열 선언
  let freshStuff = [];

  // 상한 재료들을 걸러줄 반복문 작성(0이 3개 이상)
  for (let i = 0; i < stuffArr.length; i++) {
    let str = String(stuffArr[i])
      .split('')
      .filter(e => e === '0');
    if (str.length < 3) {
      freshStuff.push(stuffArr[i]);
    }
  }

  // 신선한 재료가 필요한 재료의 수보다 부족하다면 레시피를 만들 수 없음
  if (freshStuff.length < choiceNum) {return [];}

  // 재료들을 순서대로 정렬하자
  freshStuff.sort((a,b) => a - b);

  // 더 많거나 같다면, 재료들로 만들수 있는 레시피의 경우의 수를 모두 구한다
  // 레시피를 담아줄 배열 선언
  let recipe = [];
  // 순열을 만들어줄 재귀함수를 구현
  const maker = (arr, cur, num) => {
    // num이 0이 될 때 종료되는 재귀 조건
    if (num === 0) {
      recipe.push(cur);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      // 하나를 선택하고
      const now = arr[i];
      // 배열을 슬라이스로 복사
      const sliceArr = arr.slice();
      // 선택한 것만 빼주고
      sliceArr.splice(i,1);
      // 나머지를 재귀한다, 현재 배열에는 이번에 골라낸 재료를 넣어준다
      maker(sliceArr, cur.concat(now), num - 1);
    }
  }
  // 재귀 함수를 실행해준다
  maker(freshStuff, [], choiceNum);
  return recipe;
}

4. 레퍼런스

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