[Algorithm] 순열의 순서

문제

1부터 N까지 이루어진 수열이 있을 때, 각 숫자가 한 번씩만 등장하는 수열을 순열이라고 한다.

임의의 순열은 정렬 할 수 있다. 예를 들어 N=3인 경우 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]의 순서로 생각할 수 있다.

숫자 N과 임의의 순열 K가 주어질 때, 이 순열이 몇 번째 순열인지 출력하시오.

문제 이해하기

N=4, K=[3, 4, 1, 2]일 때, 가장 먼저 K의 0번째 인덱스를 검토한다.

1. [3, x, x, x]인 배열은 그 앞 순서로 K[0]이 1인 순열, K[0]이 2인 모든 경우의 수가 존재한다.

-K[0]이 1일 때, 0번째 인덱스는 고정되어 있으므로 나머지 3자리 순열의 경우의 수를 고려하면 3!
-K[0]이 2일 때도 마찬가지로 3!
=> 2*3!

2. [3, 4, x, x]인 배열은 그 앞 순서로, K[1]이 1, K[1]이 2인 모든 경우의 수가 존재한다. 3은 이미 사용된 숫자이니 고려하지 않는다.

=> (3-1)*2!

3. [3, 4, 1, x]인 배열은 1보다 작은 숫자가 없으므로 계산할 필요가 없다.

4. [3, 4, 1, 2] 마지막 인덱스의 숫자는 이미 결정되어 있으므로, 계산할 필요가 없다.

풀이1: 반복문

function orderOfPresentation (N, K) {
  
  function factorial(n){
    let fac = [0, 1];
    for(let i = 1; i <= n; i++){
      if(fac[n] === undefined){
        fac[n] = n*factorial(n-1)
      }
    }
    return fac[n];
  }

  let result = 0;
  const including = [];

  for(let i = 0; i < N; i++){
    for(let j = 1; j < K[i]; j++){
      //including에 포함되지 않은 숫자만 카운트한다.
      if(!including.includes(j)){
        result += factorial(N-(i+1));
      }
    }
    including.push(K[i]);  
  }

  return result;
 

다른 분 코드를 참고하여 작성했던 코드.
당시엔 재귀적 사고에 익숙하지 않아서 반복문이 더 이해하기 쉬웠다.
그리고 결과값을 곱셈 없이 덧셈으로만 연산하기 때문에, 이 코드가 더 보기 편했던 이유 중 하나.

풀이2: 재귀

function orderOfPresentation (N, K) {
  function factorial(num){
    if(num <= 1){
      return 1;
    }
    return num * factorial(num-1);
  }

  const el = [];
  for(let i = 1; i <= N; i++){
    el.push(i);
  }  

  let result = 0;

  function getOrder(arr){
    //base case: 배열 길이가 1이면 모든 원소가 이미 확정된 상태이므로 탈출
    if(arr.length === 1){
      return result;
    }

    let head = arr[0];
    let tail = arr.slice(1);
    
    //indexOf 메소드를 사용해 head보다 작은 숫자를 조회
    result += (el.indexOf(head))*factorial(tail.length);
    el.splice(el.indexOf(head), 1);
    
    //배열의 뒷부분부터 다시 조회
    return getOrder(tail);
  }

  return getOrder(K);
}

참고 없이 직접 작성해본 코드.
나도 including 배열을 사용했으면 더 깔끔한 코드가 되었을 것 같은데, element를 조회해서 배열을 만들고 삭제하느라 쓸데없는 과정이 늘어난 느낌…

그래도 indexOf와 length 메소드를 사용하니까 1을 더하고 빼는 과정을 생략해도 돼서 편했다.

드디어 재귀로 코드를 짜는데 익숙해졌다는 게 뿌듯…🥲

알고리즘 문제 처음 시작하고 너무 어려워서 몇날 며칠을 고민했던 문제였는데…
한달동안 알고리즘 단련하니까 드디어 레퍼런스 참고 없이 혼자 풀 수 있게 됐다는게 기쁘다…💃