알고리즘 문제 풀이 - orderOfPresentation

문제

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

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

김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.

총 조의 수 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 <= 12인 조의 개수

인자 2: K

• Number타입의 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이 됩니다.

주의사항

• k내에 중복되는 요소는 없다고 가정합니다.

입출력 예시

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) {

// 팩토리얼 함수를 미리 선언해준다.
  const factorial = (n) => {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
  };

  let order = 0;
  
  // 모든 요소를 false로 채운다.
  // 여기서 N+1을 사용하는 이유는 인덱스는 0부터 시작하지만 조는 1조부터 있기 때문
  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;
}

 

💡 fill ()

: fill 메소드를 이용하면 배열의 시작 인덱스부터 끝 인덱스의 이전까지 갑 하나로 채운다.

const array1 = [1, 2, 3, 4];

// 인덱스 2부터 4까지 0으로 채움
console.log(array1.fill(0, 2, 4));
// expected output: [1, 2, 0, 0]

// 인덱스 1번부터 전부 5로 채움
console.log(array1.fill(5, 1));
// expected output: [1, 5, 5, 5]

// 모든 요소를 6으로 채움
console.log(array1.fill(6));
// expected output: [6, 6, 6, 6]

 

💡 slice()

: slice 메소드는 배열의 일부분 혹은 부분 배열을 반환한다. 이 메소드는 전달인자를 두개를 받는데, 각 인자는 반환될 부분의 처음과 끝을 가각 명시한다.

const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];

console.log(animals.slice(2));
// expected output: Array ["camel", "duck", "elephant"]

console.log(animals.slice(2, 4));
// expected output: Array ["camel", "duck"]

console.log(animals.slice(1, 5));
// expected output: Array ["bison", "camel", "duck", "elephant"]

console.log(animals.slice(-2));
// expected output: Array ["duck", "elephant"]

console.log(animals.slice(2, -1));
// expected output: Array ["camel", "duck"]

console.log(animals.slice());
// expected output: Array ["ant", "bison", "camel", "duck", "elephant"]

 

💡 Tip 아닌 Tip

: 중간중간 console.log를 계속 찍어보면서 단계단계 확인하는 것도 이해하는데 도움이 됨!

function orderOfPresentation(N, K) {

  // 팩토리얼 함수를 미리 선언해준다.
    const factorial = (n) => {
      if (n <= 1) return 1;
      return n * factorial(n - 1);
    };
  
    let order = 0;
    
    // 모든 요소를 false로 채운다.
    // 여기서 N+1을 사용하는 이유는 인덱스는 0부터 시작하지만 조는 1조부터 있기 때문
    const isUsed = Array(N + 1).fill(false);
  
    for (let i = 0; i < K.length; i++) {
      const num = K[i];
      console.log("num",num);
      isUsed[num] = true;
      const candidates = isUsed.slice(1, num);
      console.log("candidates",candidates);
      const validCnt = candidates.filter((el) => el === false).length;
      console.log("validCnt",validCnt);
      const formerCnt = validCnt * factorial(N - i - 1);
      console.log("formerCnt",formerCnt);
      order = order + formerCnt;
     
    }
    
    return order;
  }