[algorithm case] 가위바위보

Hyebin·2021년 5월 1일
0

Data structure / Algorithm

목록 보기
11/19
post-thumbnail
post-custom-banner

문제

가위바위보 게임은 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 동안 선택할 수 있는 모든 경우의 수를 리턴하도록 함수를 작성해 보세요.


접근 방식

문제를 접했을 때 특정 패턴을 찾고자 rock일 때 선택 가능한 경우의 수를 생각해보았다.

//중요도는 'rock', 'paper', 'scissors' 순
//rock일 때 선택 가능한 경우의 수 : 9
//rock, rock, rock
//rock, rock, paper
//rock, rock, scissors
//rock, paper, rock
//rock, paper, paper
//rock, paper, scissors
//rock, scissors, rock
//rock, scissors, paper
//rock, scissors, scissors

저렇게 적어보며 특정 패턴을 찾았다!
세번의 라운드를 돌면서 매 라운드마다 rock, paper, scissors를 모두 선택할 수 있다.

즉, 라운드마다 동일한 선택이 반복된다는 것.
반복되는 형태의 선택은 재귀로 접근하면 되겠단 생각이 들었다.

재귀로 어떻게 짤까

우선 재귀의 종료 조건을 고려했다. 마지막 라운드 진행시까지 재귀를 돌리고, 마지막 라운드일 때는 경우의 수를 담은 배열을 배열에 집어넣자.

  • 종료조건으로 수령할 방법
    해당 라운드가 끝남을 1씩 빼주며 0에 가까워지자

작성코드

const rockPaperScissors = function (rounds) {
 rounds = 3 || rounds //rounds 인자가 안들어올 때는 기본 3라운드 진행
  
 let rps = ['rock', 'paper', 'scissors'] //가중치순으로 가위바위보 배열 생성 
 let result = [] //리턴 값을 위한 배열 생성 
 
 let func = (play,round) => {
   //재귀 종료조건 (base case)
   if(round === 0) {
     result.push(play)
     return; 
   }
   //재귀 호출 
   rps.forEach(el => { 
     return func(play.concat(el), round-1)
   })
 }
 
 func([],rounds)
 return result
}

문제풀며 놓친 것들

  • base case에 return이 없어도 재귀호출이 종료될거란 착각
if(round === 0) {
     result.push(play)
}

종료 조건을 주고 재귀로 얻은 게임 결과를 result에 푸쉬해줄 생각만했지 재귀함수라는 것을 간고했다.
return값이 없으니 round가 0이 되어도 끝나지 않고, 음수까지 무한대로 돌아가는 Maximum call 현상이 발생해버렸다.

post-custom-banner

0개의 댓글