알고리즘의 time complexity...

for문안에 재귀를 돌리게되면 time complexity는 매우 높아지게 된다.

따라서 최대한 for문이 적게 돌게끔 설계를 해줘야 큰 입력이 들어와도 감당이 된다.

문제

말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.

선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.

김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤, 선생님께서 숫자를 말하면 그 순서에 맞는 경우의 수를 말해야 하고, 발표 순서를 말하면 이 발표순서가 몇번째 경우의 수인지를 대답해야 합니다.

총 학생의 수 N과 선생님이 말하는 k가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.

모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다. ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

입력

인자 1: n

• Number 타입의 1 <= N <= 20인 조의 갯수

인자 2: k

• k가 Number 일 때, k번째 배열을 리턴합니다.

ex) n이 3이고 k가 3일 경우

모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,

반환하는 값은 [2, 3, 1]이 됩니다.

• k가 Array일 때, 몇 번째인지를 리턴합니다. (0 <= index 입니다.)

ex) n이 3이고 k가 [2, 3, 1]일 경우

모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,

반환하는 값은 3이 됩니다.

function orderOfPresentation(n, k) {
  // TODO: 여기에 코드를 작성합니다.
  let numbers = []
  for(let i = 1; i<=n ; i++){
    numbers.push(i)
  }
  //obj에다가 key를 경우의 수로 두고 value를 boolean으로 줘서 이미 사용했던 숫자인지 판별
  //만들었던 숫자이면 for문 안에서 numbers의 인덱스를 올려서 숫자 조합하기.
  //n이 몇이 될지 모르니까 재귀를 통해서 구현해야한다.
  //조합한 숫자는 result에 담고 obj에 키로 추가
   //사용했던 카드의 정보를 담아야한다
  
  let result = []
  // let rec = (obj = {} ,combinated = '') =>{
  //   for(let i = 0; i < numbers.length; i++){//카드들을 순회   
  //     //카드를 선택하기전에 사용가능한 카드인지 확인         
  //     if(obj[numbers[i]] === true || obj[numbers[i]] === undefined){//사용 가능한 카드
  //       combinated += numbers[i]//카드를 선택하고
  //       obj[numbers[i]] = false //사용했던 카드로 표시
  //       console.log('combinated: ', combinated)
  //       console.log('obj[numbers[i]]: ', obj[numbers[i]])

  //       //그다음 카드를 선택하기 위해 재귀
  //       if(combinated.length < n){
  //         console.log("재귀-----------")
  //         combinated = rec(obj,combinated)
          
  //       }
  //       else{//카드가 다 만들어지면 체크 
  //       let strArr = combinated.split('')
  //       let numArr = strArr.map((el)=>Number(el))
  //       //result에 넣기전에 숫자로 변환시키기
  //       result.push(numArr)              
  //       console.log('result: ', result)
  //       }
  //       combinated = combinated.slice(0,-1) //다음 숫자 확인을 위해 썼던거 뺴주기
  //       obj[numbers[i]] = true //재귀가 끝났으니 다시 사용 가능하게 해줌
  //     }
  //     console.log("obj: ", obj)
  //     console.log('end of for loop @@@@@@@@@@@@@@@@@@@@')
            
  //   }    
  //   return combinated
  // }
  // rec()
  //위의 코드는 나의 코드인데 아래 코드처럼 순회해야하는 배열 자체를 줄여주면 더 효율적으로 순회할 수 있다
  const permutation = (arr, m = []) => {
    // 탈출 조건을 생성합니다.
    // arr의 length가 0일 때 result에 만들어진 발표 순서 배열을 담습니다.
    if (arr.length === 0) {
      result.push(m);
    } else {

      // 순열의 재료가 담긴 배열을 순환합니다.
      for (let i = 0; i < arr.length; i++) {
        // 현재 배열을 카피합니다. (원본을 건드리면 모든 경우의 수를 찾을 수 없습니다.)
        let currentArray = arr.slice();
        // 제일 앞에 있는 요소를 가지고 와서 변수에 할당합니다.
        let element = currentArray.splice(i, 1);
        // 제일 앞에 있는 요소가 사라진 배열 ([1, 2, 3]이었다면 현재는 [2, 3])을 arr 인자에 넣고, m 배열과 element를 합쳐서 m 인자에 넣습니다.
        permutation(currentArray.slice(), m.concat(element));

        // 이렇게 되면 다음은 [2, 3]을 카피하고, element가 [2]가 될 것이며
        // 제일 앞에 있는 요소가 사라진 배열 [3]이 arr에 들어갈 것이고, element는 m과 다시 합쳐져 [1, 2]를 만들 것입니다.
        // 이렇게 계속 재귀를 돌려서 m이 [1, 2, 3]이 되면, arr의 lenght는 0이 될 것이고, 재귀에서 빠져나옵니다.
        // arr === []일 때(m이 [1, 2, 3]) result에 push를 하여 함수를 종료하고, 그다음 arr === [3]일 때(m이 [1, 2]) for문의 길이가 1이었으므로 함수를 그대로 종료하고,
        // arr === [2, 3]일 때(m이 [1]) for문은 arr.length에 따라 2번 돌기 때문에 2를 지나 3이 될 것입니다.
        // [1] => [1, 3] => [1, 3, 2] => (1의 모든 경우의 수를 다 돌았으니 2로 진입) [2] => [2, 1] => [2, 1, 3] ...
      }
    }
  };

  permutation(numbers);
  console.log('final result: ', result)
  //리턴
  if(Array.isArray(k)){
    return result.findIndex((el)=>{
      return String(el) === String(k)
    })    
  }else{
    return result[k]
  }
}
orderOfPresentation(5,3) //5만들어오게 되도 경우의수가 120가지, 9가 들어오게되면 36만가지가된다.