조 발표 순서 계산 알고리즘

function orderOfPresentation(N, K) {
    // 조의 개수 N, 발표 순서 K

  
    const factorial = (n) => {
      if (n <= 1) return 1;
      return n * factorial(n - 1);
    }; //팩토리얼 n!
  
    let order = 0;
    
    // N개의 조 중에, 어떠한 조가 이미 포함되었는지 확인하기 위해 배열을 생성
    // 제일 첫 번째는 더미 데이터
    const isUsed = Array(N + 1).fill(false);
    
    for (let i = 0; i < K.length; i++) {
      // K의 i번째 조를 변수에 담는다.
      const num = K[i];
      // 사용했으면 true
      isUsed[num] = true;
      //1부터 num-1의 배열을 복제해서,
      const candidates = isUsed.slice(1, num);
      // 사용하지 않는 수의 개수를 구한다.
      const validCnt = candidates.filter((el) => el === false).length;
      // 사용하지 않은 수의 경우의 수를 카운트한다.
      const formerCnt = validCnt * factorial(N - i - 1);
      // order에 추가
      order = order + formerCnt;
  
     
    }
    
    return order;

인덱스 0에는 아무 데이터나 넣어놓고, 실제 조의 번호를 사용할 때는 인덱스 1부터 사용하는 방법을 사용하고,

인덱스 0은 더미 데이터로 사용

 

ex ) 3, [2,3,1]

IsUsed [ false , false , false ,false]

candidate = [ false]로 validCnt는 1이 된다.

formerCnt = 1 * factorial(3 - 0 - 1)

order는 2 추가

 

IsUsed [false, false, true, false]

candidate = [false] validCnt는 1이 된다.

formerCnt  = 1 * factorial(3 - 1 - 1)

order는 1 추가

 

IsUsed [false, true, true, true]

candidate = [] validate는 0이다.

formerCnt는 0

 

order는 3

 

 

 

각 조가 선택될 때, 그 전에 이미 선택된 조들의 경우의 수는 (해당 조 앞에 올 수 있는 사용되지 않은 조의 수) * (앞으로 선택해야 하는 모든 조의 경우의 수)