[중복순열] 가위바위보

가위바위보

문제

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

입력

• 없음

출력

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

주의사항

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

입출력 예시

let output = rockPaperScissors();

console.log(output);
/*
    [
      ["rock", "rock", "rock"],
      ["rock", "rock", "paper"],
      ["rock", "rock", "scissors"],
      ["rock", "paper", "rock"],
      // ...etc ...
    ]
  */

Advanced

• 가위바위보 게임의 수를 나타내는 양의 정수 rounds가 인자로 주어질 경우, 해당 rounds 동안 선택할 수 있는 모든 경우의 수를 리턴하도록 함수를 작성해 보세요.

let output = rockPaperScissors(5);

console.log(output);
/*
    [
      ["rock", "rock", "rock", "rock", "rock"],
      ["rock", "rock", , "rock", "rock", "paper"],
      ["rock", "rock", , "rock", "rock", "scissors"],
      ["rock", "rock", "rock", "paper", "rock"],
      ["rock", "rock", "rock", "paper", "paper"],
      ["rock", "rock", "rock", "paper", "scissors"],
      ["rock", "rock", "rock", "scissors", "rock"],
      // ...etc ...
    ]
  */

문제풀이

function rockPaperScissors () {
  const rps = ['rock', 'paper', 'scissors'];
  const result = [];
  // 재귀함수 
  function generateCombinations(curr, count) {
    // 1. 재귀 종료조건. 선택한 갯수가 3개면, 현재 조합을 결과에 추가
    if(count === 3) {
      result.push(curr);
      return;
    }
    // 2. 재귀 탐색. 3개 미만이면, 모든 선택지를 현재 조합에 추가하고 선택한 개수를 1 증가시킨 후, 재귀 호출
    for(const choice of rps) {
      generateCombinations(curr.concat(choice), count+1);
    }
  }
  // 가능한 모든 조합 만들기위해, 빈 배열과 선택한 개수 0으로 재귀 함수 호출
  generateCombinations([], 0);
  return result;
};

가능한 모든 가위바위보 조합을 생성하는 재귀 함수를 사용합니다. 재귀 함수는 현재까지 선택한 조합을 배열로 받고, 선택한 개수를 세는 변수를 인자로 받습니다. 선택한 개수가 3개이면, 현재까지 선택한 조합을 결과 배열에 추가합니다. 선택한 개수가 3개 미만이면, 모든 가위바위보 선택지를 현재까지의 조합에 추가하고, 선택한 개수를 1 증가시킨 후, 재귀적으로 함수를 호출합니다. 모든 가능한 조합을 생성한 후, 이를 담은 배열을 반환합니다.

어드밴스 추가

function rockPaperScissors(rounds = 3) {
  const rps = ["rock", "paper", "scissors"];
  const result = [];

  const generateCombinations = (count, arr, bucket, result) => {
    // count가 0이면 bucket 배열에 저장된 요소들로 이루어진 새로운 조합을 result 배열에 추가하고 종료
    if (count === 0) {
      result.push(bucket);
      return;
    }

    // arr 배열의 요소를 반복하며 재귀적으로 조합 생성
    for (let i = 0; i < arr.length; i++) {
      const pick = arr[i];
      // 현재 선택한 요소를 bucket 배열에 추가하고 count를 1 감소시켜 재귀호출
      generateCombinations(count - 1, arr, bucket.concat(pick), result);
    }
  }


  // 라운드 수와 rps 배열, 빈 배열, 결과를 저장할 result 배열을 전달하여 모든 조합 생성
  generateCombinations(rounds, rps, [], result);
  return result;
};

rounds 매개변수가 전달되지 않으면 기본값인 3을 사용합니다.

(rounds = 3) 구문은 기본 매개변수 문법을 사용한 것입니다. rounds 매개변수가 함수 호출 시 제공되지 않을 경우, 3이 기본값으로 사용된다는 것을 의미합니다.
rounds = rounds || 3 과 동일한 결과를 나타내는 방식으로, rounds 변수에 값이 할당되지 않았거나 undefined일 경우에만 3을 할당합니다.
즉, rounds 변수가 함수에 전달되지 않으면 기본값 3을 사용하도록 설정하는 방법입니다.

먼저 rps 배열에는 가위, 바위, 보 세 가지 요소가 포함됩니다. 그리고 generateCombinations 함수는 이 배열에서 조합을 생성합니다. count 매개변수는 생성할 요소의 수를 나타냅니다. bucket 배열에는 이전 단계에서 선택한 요소가 포함되어 있습니다. result 배열은 가능한 모든 조합을 저장합니다.

if (count === 0) {
  result.push(bucket);
  return;
}

count 값이 0이면, 즉 모든 요소가 선택되었을 때, bucket 배열을 result 배열에 추가합니다.

for (let i = 0; i < arr.length; i++) {
  const pick = arr[i];
  generateCombinations(count - 1, arr, bucket.concat(pick), result);
}

 

그렇지 않으면, arr 배열의 요소를 반복하여 가능한 모든 조합을 생성합니다. bucket 배열에 현재 선택한 요소를 추가하고, count를 1 감소시켜 재귀 호출합니다. 이 과정을 모든 요소가 선택될 때까지 반복합니다.

레퍼런스코드

// Advanced가 포함된 레퍼런스 코드입니다.
const rockPaperScissors = function (rounds) {

  // rounds 매개변수를 임의로 넣습니다.
  // rounds 변수가 있을 경우 그대로 사용하고, 없다면 3(기본)을 사용합니다.
  rounds = rounds || 3;
  const rps = ['rock', 'paper', 'scissors'];

  // 결과를 담을 배열 선언
  const outcomes = [];

  // 재귀를 사용할 함수 선언
  // rounds를 넣을 변수 roundsToGo, 일회용 배열인 playedSoFar 변수를 선언합니다.

  // 재귀를 사용하는 이유는, 배열의 모든 요소의 경우의 수를 훑기 위한 적절한 방법이기 때문입니다.
  // 간단히 말하자면, 이 함수는 rounds 숫자를 기준으로, 일회용 배열에 rps 요소를 rounds 숫자만큼 넣게 됩니다.
  // 이 로직을 잘 이해할 수 있을 때까지 하단의 함수 로직을 연구해야 합니다.
  let permutate = function (roundsToGo, playedSoFar) {

    // rounds가 0일 경우 outcones 배열에 삽입하고, 재귀에서 빠져나옵니다.
    if (roundsToGo === 0) {
      outcomes.push(playedSoFar);
      return;
    }

    // rps 배열을 한 번씩 순회합니다.
    for (let i = 0; i < rps.length; i++) {
      // rps의 i번째 요소를 변수에 담아서
      let currentPlay = rps[i];
      // permutate(본인)에 기존 rounds에서 하나 뺀 숫자와, 일회용 배열 playedSoFar에 currentPlay를 삽입하여 재귀를 실행합니다.
      // rounds에서 하나를 빼는 이유는, 일회용 배열의 크기를 rounds만큼 맞춰주기 위함입니다. [rock, rock, rock]

      // Q. playedSoFar.push(currentPlay)로 할 수 있을 텐데, 왜 concat을 사용할까요?
      permutate(roundsToGo - 1, playedSoFar.concat(currentPlay));
      /**
       * 이 재귀의 로직은 이렇습니다. 처음 실행된 반복문은 rps를 전부 순회해야 끝이 납니다.
       * 그러나 한 번 반복할 때마다 permutate 함수가 실행되고, rounds의 숫자는 짧아지며, playedSoFar에 요소가 계속 쌓일 것입니다.
       * 결국, roundsToGo가 0이 될 때까지 이 반복문은 rps[i]가 0일 것이며, playedSoFar에는 [rock, rock, rock]이 되어 outcones에 Push하고, 종료하게 됩니다.
       * return이 되었으니, 한 번의 재귀 호출이 끝났습니다. 마지막 호출 바로 전으로 돌아가,
       * for문은 i = 1을 가리키게 될 것이고, [rock, rock, paper]을 삽입한 뒤 호출을 하게 됩니다.
       * roundsToGo가 0이 되어, 해당 배열은 outcomes 배열에 삽입됩니다.
       * 이런 식으로 모든 호출의 반복문이 끝날 때까지 반복하며 outcomes에 경우의 수 요소들이 담기게 됩니다.
       */
    }
  };

  // 함수를 실행합니다.
  permutate(rounds, []);

  // outcomes를 반환합니다.
  return outcomes;
};