210811_문제노트_순열

Bitnara Lee·2021년 8월 11일

새로운 치킨 소스 레시피

문제

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

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

입력

인자 1: stuffArr

Number 타입의 재료를 담은 배열
- 요소는 0과 1로만 이루어진 숫자이며, 항상 1로 시작합니다.
- 요소는 중복될 수 없습니다.
- 요소의 길이는 20 이하입니다.
- 배열의 길이는 2 이상 10 이하입니다.
- ex) [111, 110, 1010, 10, 10110]

인자 2: choiceNum

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

출력

Number 타입을 반환해야 합니다.
- stuffArr가 [1, 10, 11000, 1111] 이고, choiceNum은 2라면 사용 가능한 재료는 [1, 10, 1111] 입니다. 조합할 수 있는 경우의 수는 6 가지입니다.

주의사항

만약, 주어진 재료 모두 사용할 수 없다면 빈 배열[]을 반환해야 합니다.
만약, 사용할 수 있는 재료가 choiceNum보다 작다면 빈 배열[] 을 반환해야 합니다.
조합 및 요소는 작은 숫자 -> 큰 숫자로 정렬합니다.
- 예시로 [1, 10, 11000, 1111]이 요소로 들어왔다면, 0이 세 개인 11000을 제외하고 [1, 10, 1111] 순서가 되어야 하며,
  [ [1, 10], [1, 1111], [10, 1], [10, 1111], [1111, 1], [1111, 10] ]을 반환해야 합니다.

입출력 예시

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

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

< CODE >

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

 /*  내 코드(이렇게도 가능)
 
 stuffArr = stuffArr.filter(stuff => { // 필터해서 나와야할 것은 0 세개인 요소를 제외한 배열 
     strstuff = String(stuff).split('')
     let count = strstuff.filter(el => el === '0').length
     return count < 3 //or stuff 속 3의 length가 <3
   })   */

  
  
  // 정렬
  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;
}


/* 내 코드(bucket.length가 choiceNum이 될때를 리턴 조건으로 줄 수도 있다)

 const recurs = (arr=stuffArr, bucket=[])=>{
       if(bucket.length === choiceNum){
         result.push(bucket)
         return;
       }
       for(let i=0; i< arr.length; i++){
       let clone = arr.slice()    // 이걸 안해주면 나중에 회귀할때 돌아오지 못한다. 그냥 []
       let choice = clone.splice(i,1)
       recurs(clone, bucket.concat(choice))
       } 
   }
   */

배열에 대해 중복순열이 아닌 순열을 구할시

🔰 중복되지 않도록 넣어주는 i번째를 제거해야 한다.

🔰 재귀의 인자로 기존배열과 choiceNum, 요소들 담을 배열(혹은 담을 배열과 기존배열)을 받아
for문 안에서 기존 배열을 slice() 한 후 splice(i,1)로 하나씩 뽑는다.

🔰 그 후 요소들을 담아서 재귀시킨다.