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

새로운 치킨 소스 레시피

문제

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

1. 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.
2. 재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다.
   단, 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다.
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],
    [1100, 1], [1100, 10], [1100, 1111],
    [1111, 1], [1111, 10], [1111, 1100]
  ];
*/

📌 해당 문제에서는 먼저 예외 조건을 적용해 주어 입력된 배열을 수정해줘야 한다. 이걸 먼저 안해줘서 답을 애 먹었다.

1. 사용할 수 있는 재료가 choiceNum보다 작다면 빈 배열[] 을 반환해야 합니다. 조건을 만족시킨다.
2. 들어온 배열에서 0이 3개 있는 인덱스를 제외 시키고 오름차순으로 정렬한다. (정규식 활용)
3. 해당 배열의 인덱스를 통해 중복되지 않는 수를 만들기 위해 ch 배열을 만든다.
4. 케이스를 기록할 tmp 배열을 만든다.
5. 들어온 배열을 순회하며 탐색한다.
6. 중복된 숫자를 tmp에 넣지 않기위해 ch 배열을 활용해 동일한 인덱스는 제외시킨다.
7. 레벨이 choiceNum, 즉 원하는 수만큼의 노드를 파고들었을 때 tmp를 answer에 푸쉬해준다.

function newChickenRecipe(stuffArr, choiceNum) {
    if ( choiceNum > stuffArr.length ) {
        return [];
    }
  	// 0이 3개인 요소 제외
    let filterArr = stuffArr.filter((index) => !/0{3,}/g.test(index))
    let sortStuff = adStuff.sort((a,b) => a-b);

    let answer = [];
    // 조건에 부합하는 배열
    let tmp = Array.from({ length: choiceNum }, () => 0);
    //요소가 중복되면 안되므로 ch 배열 필요
    let ch = Array.from({ length: stuffArr.length }, () => 0);

    const DFS = (L) => {
        if ( L === choiceNum) {
            answer.push([...tmp])
        }
        else {
            for ( let i = 0; i < sortStuff.length; i++ ) {
                if (ch[i] === 0 ) {
                    ch[i] = 1;
                    tmp[L] = sortStuff[i]
                    DFS(L+1);
                    ch[i] = 0;
                }
            }
        }
    }

    DFS(0)
    return answer;
}

console.log(newChickenRecipe([1, 10, 1100, 1111], 2));