TIL 11주차 3일 - 순열,조합,공약수

최대 공약수

• 유클리드 호제법

function gcd (a,b){
   if(a%b === 0){
      return b
   }
   return gcd (b, a%b)

순열

• 중복 상관 없을 시

function rockPaperScissors (rounds) {

  let rps = ['rock', 'paper', 'scissors']
  let outcomes = [];
  rounds = rounds || 3;
  
  // 재귀함수를 만든다.
  let permutate = function (temp, rounds){
    // 재귀함수 종료 조건
    if(rounds === 0){
      outcomes.push(temp)
      return
    }
   
   // 재귀함수 실행문
    for(let i=0; i < rps.length; i++){
      permutate(temp.concat(rps[i]), rounds-1)
    }
  }
  
  // 재귀함수 실제 실행
  permutate([], rounds)

  return outcomes

};

• 중복 상관 있을 시

function newChickenRecipe(stuffArr, choiceNum) {
  // 결과물 변수를 만든다.
  let result = []
  
  // 000 이 3개 이상인 요소를 필터링한다.
  function checked (num){
    let count = 0;
    let arr = String(num).split('')
    for(let i=0 ; i < arr.length; i++){
      if(arr[i] === '0'){
        count++
      }
    }
    if(count >=3) {
      return false
    }else {
      return true
    }
  }
  
  let filterStuffArr = stuffArr.filter(checked)

  // 오름차순으로 정렬한다.
  filterStuffArr.sort((a,b)=>a-b)

  // 특이 케이스 처리한다.
  if(filterStuffArr.length === 0 || filterStuffArr.length < choiceNum){
    return result
  }
  
  // 순열 함수를 새로 만든다.
  function permutate (arr, temp, num){
    if(num === 0){
      result.push(temp)
      return
    }
	
    // 중복 요소를 없애기 위하여 새로운 배열을 만들어 재귀함수 돌린다.
    for(let i=0; i < arr.length; i++){
      let choice = arr[i]
      let sliceArr = arr.slice()
      sliceArr.splice(i,1)
      permutate(sliceArr, temp.concat(choice), num-1)
    }
  }


  // 순열 함수를 실행한다.
  permutate(filterStuffArr, [], choiceNum)

  // 결과물 변수를 리턴한다.
  return result

}