Toy #1 orderOfPresentation

문제

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

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

let output = orderOfPresentation(3, [2, 3, 1]);
console.log(output); // 3

output = orderOfPresentation(5, [1, 3, 2, 4, 5])
console.log(output); // 6

풀이

function orderOfPresentation (N, K) {

  // N = 3 일 경우, 경우의 수 총 6가지 => 3 x 2 x 1 = 6 (순열)
  
  const factorial = (n) => {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
  };

  // 리턴할 값 변수 생성
  let result = 0;
  
  // 이미 포함된 조를 파악하기 위해 false로 채워진 배열 생성
  // (+1 : 인덱스는 0부터 시작하지만 조는 1부터 시작하기 때문)
  const isUsed = Array(N + 1).fill(false);
  
  for (let i = 0; i < K.length; i++) {
    
    // K 배열의 i번째 수를 사용했는지 판별하기 위해, 그 값을 num 변수에 할당하고,
    // 그 num을 index 삼아 isUsed 배열 값을 true로 변경
    // (이 문제의 경우 중복 값이 없기 때문에 가능함)
    const num = K[i];
    isUsed[num] = true;
 
    // num 보다 앞에 올 수 있는 수들의 배열을 복제한 후,
    // 그 배열 안에 있는 false의 개수를 구함
    const candidates = isUsed.slice(1, num);
    const falseCount = candidates.filter((x) => x === false).length;
    
    // 아직 사용되지 않은 수, 그 전까지의 모든 경우의 수를 카운트
    const realCount = falseCount * factorial(N - i - 1);
    result += realCount;

   }
   
  return result;
    
}

/*
 N = 5, K =[1, 3, 2, 4, 5] 일때의 과정 풀이
 
 1. i = 0, num = K[0] = 1, isUsed[1] = true
 isUsed = [false, true, false, false, false, false]
 candidates = isUsed.slice(1, 1) = []
 falseCount = 0
 realCount = 0
 result = 0
 
 2. i = 1, num = K[1] = 3, isUsed[3] = true
 isUsed = [false, true, false, true, false, false]
 candidates = isUsed.slice(1, 3) = [true, false]
 falseCount = 1
 realCount = 1 * factorial(5 - 1 - 1) = 1 * factorial(3) = 6
 result = 6
 
 3. i = 2, num = K[2] = 2, isUsed[2] = true
 isUsed = [false, true, true, true, false, false]
 candidates = isUsed.slice(1, 2) = [true]
 falseCount = 0
 realCount = 0
 result = 6
 
 4. i = 3, num = K[3] = 4, isUsed[4] = true
 isUsed = [false, true, true, true, true, false]
 candidates = isUsed.slice(1, 4) = [true, true, true]
 falseCount = 0
 realCount = 0
 result = 6
 
 5. i = 4, num = K[4] = 5, isUsed[5] = true
 isUsed = [false, true, true, true, true, true]
 candidates = isUsed.slice(1, 5) = [true, true, true, true]
 falseCount = 0
 realCount = 0
 result = 6
 */