Question
개업 이래로 항상 승승장구하는 '승승장구 치킨집'의 비결은 소스에 있다. 수많은 타사 브랜드 치킨집들이 승승장구 치킨집의 소스 비결을 알아내려고 했으나 빈번히 포기했다.
그 이유는 5대째 내려오는 '비밀의 승승장구 치킨 소스 비율 레시피'는 70억 인구 중 사장님만 알고 있기 때문이다. 최근, 누리꾼 사이에서 이 레시피의 일부분을 발췌했다는 소문을 듣게 되었다.
그 소문은 다음과 같다.
1.
N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.
2.
재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다.
a.
단, 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] ]을 반환해야 합니다.
Test Case 1
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]
]
*/
Shell
복사
Test Case 2
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],
]
*/
Shell
복사
Solve
function newChickenRecipe(stuffArr, choiceNum) {
const freshArr = stuffArr.filter((el) => {
let stuff = String(el);
let count = 0;
for (let i = 0; i < stuff.length; i++) {
if (stuff[i] === '0') count++;
}
return count < 3;
});
if (freshArr.length === 0 || freshArr.length < choiceNum) return [];
function permutation(arr, num) {
if (num === 1) return arr.map(i => [i]);
return arr.reduce((acc, target, idx, origin) => {
// 재료 중복되는 경우가 있음. 선택한 재료 하나만 지워야함
const rest = origin.slice();
rest.splice(idx, 1);
const pArr = permutation(rest, num - 1);
const addArr = pArr.map(el => [target, ...el])
acc.push(...addArr);
return acc;
}, [])
}
return permutation(freshArr, choiceNum);
}
JavaScript
복사
실행시간 : ms
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;
}
JavaScript
복사
실행시간 : ms