Javascript # Algorithm

📝오늘 배운 내용

오늘은 경우의 수를 구하는 알고리즘에 대해 작성해보려고 한다.
총 조의 수 N과 발표 순서 K가 이 함수의 인자로 들어왔을 때, K의 인덱스 값을 출력해야 한다.
예를 들어, N = 3이고, K = [2, 3, 1]일 때, 총 경우의 수는 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 될 것이고, 여기서 K의 인덱스 값은 3이기 때문에 3을 출력해줘야 한다.
코드를 살펴보면, 이 문제를 해결하기 위해 factorial 함수를 사용하였다.

function orderOfPresentation (N, K) {
  const factorial = (n) => {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
  };
  let order = 0;
  
  const isUsed = Array(N + 1).fill(false);
  
  for (let i = 0; i < K.length; i++) {
    const num = K[i];
    isUsed[num] = true;
    const candidates = isUsed.slice(1, num);
    const validCnt = candidates.filter((el) => el === false).length;
    const formerCnt = validCnt * factorial(N - i - 1);
    order = order + formerCnt;
  }
    return order;
}

위 코드를 손코딩해보자

const isUsed = Array(N + 1).fill(false); // [false, false, false, false]
  
  for (let i = 0; i < K.length; i++) { // K는 3이므로, 총 3번 반복한다.
    const num = K[i]; // num = 2
    isUsed[num] = true; // isUsed의 2번째 인덱스를 true로 [false, false, true, false]
    const candidates = isUsed.slice(1, num); // 1번째 인덱스부터 2번째 인덱스까지 [false, true]
    const validCnt = candidates.filter((el) => el === false).length; // false인 값만 배열에 포함
    const formerCnt = validCnt * factorial(N - i - 1); // 1 * factorial(3 - 0 - 1) = 2
    order = order + formerCnt; // order = 2
  }
    return order;

const isUsed = Array(N + 1).fill(false); // [false, false, false, false]
  
  for (let i = 0; i < K.length; i++) { // K는 3이므로, 총 3번 반복한다.
    const num = K[i]; // i는 1이되서 num = 3
    isUsed[num] = true; // isUsed의 3번째 인덱스를 true로 [false, false, true, true]
    const candidates = isUsed.slice(1, num); // 1번째 인덱스부터 3번째 인덱스까지 [false, true, true]
    const validCnt = candidates.filter((el) => el === false).length; // false인 값의 길이만큼 배열에 포함
    const formerCnt = validCnt * factorial(N - i - 1); // 1 * factorial(3 - 1 - 1) = 1
    order = order + formerCnt; // order = 2 + 1 = 3
  }
    return order;

const isUsed = Array(N + 1).fill(false); // [false, false, false, false]
  
  for (let i = 0; i < K.length; i++) { // K는 3이므로, 총 3번 반복한다.
    const num = K[i]; // i는 2가되서 num = 1
    isUsed[num] = true; // isUsed의 3번째 인덱스를 true로 [false, true, true, true]
    const candidates = isUsed.slice(1, num); // 1번째 인덱스부터 1번째 인덱스까지 [true]
    const validCnt = candidates.filter((el) => el === false).length; // false인 값의 길이만큼 배열에 포함
    const formerCnt = validCnt * factorial(N - i - 1); // 0 * factorial(3 - 2 - 1) = 1
    order = order + formerCnt; // formerCnt = 0이 된고, order = 3 그대로 남고 반복문 종료
  }
    return order;