새로운 치킨 소스 레시피
문제
개업 이래로 항상 승승장구하는 '승승장구 치킨집'의 비결은 소스에 있다. 수많은 타사 브랜드 치킨집들이 승승장구 치킨집의 소스 비결을 알아내려고 했으나 빈번히 포기했다.
그 이유는 5대째 내려오는 '비밀의 승승장구 치킨 소스 비율 레시피'는 70억 인구 중 사장님만 알고 있기 때문이다. 최근, 누리꾼 사이에서 이 레시피의 일부분을 발췌했다는 소문을 듣게 되었다.
그 소문은 다음과 같다.
- 가지의 재료 중에 단 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],
[1100, 1], [1100, 10], [1100, 1111],
[1111, 1], [1111, 10], [1111, 1100]
];
*/📌 해당 문제에서는 먼저 예외 조건을 적용해 주어 입력된 배열을 수정해줘야 한다. 이걸 먼저 안해줘서 답을 애 먹었다.
- 사용할 수 있는 재료가 choiceNum보다 작다면 빈 배열[] 을 반환해야 합니다. 조건을 만족시킨다.
- 들어온 배열에서 0이 3개 있는 인덱스를 제외 시키고 오름차순으로 정렬한다. (정규식 활용)
- 해당 배열의 인덱스를 통해 중복되지 않는 수를 만들기 위해 ch 배열을 만든다.
- 케이스를 기록할 tmp 배열을 만든다.
- 들어온 배열을 순회하며 탐색한다.
- 중복된 숫자를 tmp에 넣지 않기위해 ch 배열을 활용해 동일한 인덱스는 제외시킨다.
- 레벨이 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));