[중복순열] rockPaperScissors

👊 문제

가위바위보 게임은 2인 이상의 사람이 동시에 '가위, 바위, 보'를 외치고 동시에 가위, 바위 또는 보 중에서 한 가지를 의미하는 손 모양을 내밀어 승부를 결정짓는 게임입니다. 세 판의 가위바위보 게임을 할 경우, 한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 세 번의 선택으로 가능한 모든 경우의 수를 구하는 함수를 작성합니다.

🖐 출력

2차원 배열(arr[i])을 리턴해야 합니다.
arr[i]는 전체 경우의 수 중 한 가지 경우(총 세 번의 선택)를 의미하는 배열입니다.
arr[i]는 'rock', 'paper', 'scissors' 중 한 가지 이상을 요소로 갖는 배열입니다.
arr[i].length는 3

✌ 주의사항

최종적으로 리턴되는 배열의 순서는 가중치 적용 정렬(Weighted Sort)을 따릅니다.
중요도는 'rock', 'paper', 'scissors' 순으로 높습니다.
쉽게 생각해 올림픽 순위 결정 방식을 참고하면 됩니다.
금메달('rock')이 은메달('paper')보다 우선하고, 은메달('paper')이 동메달('scissors')보다 우선합니다.

👊 문제에 대한 이해

이 문제는 중복순열문제로, 그냥 모든 경우의수를 다 때려박으면 된다.
해당 문제로만 봤을때 한사람당 최대 세개를 낼 수 있다는 전제조건이 나왔기 때문에 3중 for문으로 다음과 같이 어렵지 않게 풀수 는 있다.

👊 풀이

function rockPaperScissors () {
  // 중복순열 : 다때려박기 1. 3중포문으로 작성해보기 
  // 세번의 선택으로 가능한 모든 경우의수
  let rps = ['rock','paper','scissors']
  let arr = [];
  // 한사람이 낼수있는 세번의 선택수 : 락락락, 락락페이퍼, 락락시저,...시저시저시저
  for(let i = 0; i<rps.length; i++){
    for(let j = 0; j<rps.length; j++){
      for(let k = 0; k<rps.length; k++){
        let el = [];
        el.push(rps[i],rps[j],rps[k])
        arr.push(el)
      }
    }
  }

return arr
};

하지만 3중 for문도 복잡해 죽겠는데 한사람당 세번이 아닌 네번, 다섯번.. 많게는 100번 낼수있는 경우의 수라면 for문을 계속적으로 쓸 수는 없다.
이럴때 매개변수를 추가하여, 해당 매개변수 값만큼의 모든 경우의 수를 나타내는 식을 작성해 보겠다.

function rockPaperScissors ( rounds ) {
  // 중복순열 : 다때려박기  2. 매개변수받아서 해보기
  rounds = rounds || 3;
  let rps = ['rock','paper','scissors']
  let arr = [];

  const recursive = (num = rounds,basket =[]) => {
    if(num === 0){
      arr.push(basket);
      return;
    }
    for(let i = 0; i<rps.length; i++){
      let cur = rps[i];
      recursive(num-1,basket.concat(cur))
    }
  }
  recursive()
  return arr;
};

recursive 케이스로, 현재의 값을 rps[i] 번째로 지정한 후, 다 i번 다돌면 num(rounds)에서 하나 감소함과 동시에 basket에 cur, 현재의 값들을 concat 하여 넣는다. 이것을 매개변수 rounds, 즉 num이 0이 될때까지 반복하여 최종적으로 arr에 basket 값을 넣어주어 리턴하도록 한다.

---

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

🍗 문제

개업 이래로 항상 승승장구하는 '승승장구 치킨집'의 비결은 소스에 있다. 수많은 타사 브랜드 치킨집들이 승승장구 치킨집의 소스 비결을 알아내려고 했으나 빈번히 포기했다.
그 이유는 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]
  ]
*/

🍗 문제에 대한 이해

0,1로만 이루어진 레시피 조합인데 10,01 은 같은 수더라도 완전히 다른 레시피이다. 이것을 따져서 모든 경우의 수를 구하는걸 봐서는 순열이다! 하고 알수있어야 한다. 전제조건으로, 0이 세번연속해서 들어가면 그건 쓰레기레시피이므로 버리고 온전한 레시피들만으로 이루어진 배열안에서 경우의 수를 구한다.
같은수가 겹치면 안되는것을 인지하도록 하자!! (중복순열처럼 다 때려박는게 아님.)

🍗 풀이

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 = [];
  const recursive = (arr=freshArr, bucket =[], n=choiceNum) => {
    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);
      recursive(sliceArr, bucket.concat(choice), n - 1);
    }
  };

  recursive();
  return result;

이전 가위바위보에서 구했던 재귀와 형태가 상당히 비슷하다.
다른점이라면, 중복순열과 달리 한번 연속으로 같은값이 나오지 않는다는 점이다.
예를들어 [1,2,3,4] 를 중복순열로 경우의수를 구한다고 했을때
[1,1,1,1],[1,1,1,2]... 이런식으로 가능했지만
순열은 [1,2,3,4],[1,2,4,3],[1,3,2,4]... 이런식으로 진행되게 된다.
즉, 같은 수이지만 순서가 바뀌면 아예다른것이 된다는 뜻이다.
다른분은 dfs 방식으로도 풀었는데 아무래도 그거보다 한번 익혀둔 방식이 더 손에 익는다.
중복순열, 순열문제는 이렇게 풀어가는게 나은것같다.

🛠 번외 - 삽질의 여정.

000이 연속으로 있는 배열을 제외하고 싶어서 생각해낸 삽질을 작성해보겠다.
뭐. 괜한 집착으로 결론적으로는 되긴되는데 단 몇줄이면 끝낼것을 돌고 돌아 풀음.(바보 ㅠ)

🛠 삽질 1. 지옥의 필터링.

  // 1. stuffArr 에서 000 솔팅하기 -> [1, 10, 11000, 1111]
  // - 각 요소에서 0이 있는것만 솔팅. includes?
  // string 으로 바꿔준다음 includes 여부따져. 
  let filtering = stuffArr.filter((el)=>{
    if(String(el).includes(0)) return el;
  }) //[10, 11000]
  filtering = String([...filtering]).split(',') //"10,11000"->["10", "11000"]
  filtering = filtering.filter((el)=>{ el.split('');
  arr.push([...el])
  })
//arr = ["1", "0"], ["1", "1", "0", "0", "0"]
// ........ 집착의 끝.

왜그렇게 생각했는지 모르겠지만 일단 stuffArr에서 0이 있는것만 추출해야겠다고 생각했다.
처음나의 수도코드는
000 추출하기 위해서 0이 있는 요소맨 필터링 => 스트링으로 바꿔준다음에 배열형태로 만들고 => 그걸 또 for 문을 돌려서 "0"이 갯수가 2개이상인것만 남겨서 숫자형배열로 만들고 그 요소가 stuffArr에 있으면 뺴고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
넘길어서 쓰지도 못하겠다. 진짜 필터 개많이씀.

아무래도 이건 아니다 싶어서 레퍼런스 코드를봤는데 애초에 stuffArr 전체 배열에서부터 0만 추출하여 0이 2보다 같거나 작을때 (해당되는 값만) 새 배열에 넣어주는 식이었다.

🛠 삽질 2. 엣지케이스 안넣어줌.

솔직히 왜넣어줘야하는지 모르겠다 이거에요.
ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ눙물