Algorithm problem-01

순열, 조합, 재귀

1. 문제

• 1번부터 N번까지의 조(1<=N<=12)
• 주어진 조를 임의로 나열한 배열 K(중복되는 요소는 없음)
• 배열 K가 조를 나열하는 경우의 수 중, 몇번째인지를 구하는 문제

2. 시도

• N개의 조를 가지고 만들수 있는 경우의 수는, 팩토리얼 N의 값
• 경우의 수를 전부 만들고, 그 중 몇번째인지를 탐색하는 방법은 사실상 불가(call stack over)
• 1개씩 고정시키고, 나머지 값의 팩토리얼을 통해서 해결하는 방법을 생각해봄
• 시간 내에 구상하지 못하고, 관련 내용만 찾아보다 종료함
• 이후 구글링을 통해 찾은 내용을 골자로 정리함

3. 수도코드

function orderOfPresentation (N, K) {
  // N개조의 전체 경우의 수를 구하는 방법은 팩토리얼
  // 1개를 고정하고 나머지의 팩토리얼을 구해서 찾아보는 방법을 생각해봤음
  // 우선은 팩토리얼을 구하는 내부 함수를 먼저 작성해 보자
  function 팩토리얼{}
  // 1부터 n까지의 수로 이루어진 임의의 배열을 작성한다
  let 임의의 배열 = [1, .... N]
  // 각각의 자리가 가진 경우의 수를 더해줄 변수를 선언해준다
  // 참고로, 발표 순서는 0번째부터 시작한다
  let result = 0;
  // while문을 가지고 K의 요소를 하나씩 빼내서 경우의 수를 구해서 더하고
  // K가 빈 배열이 되면 종료하며 누적으로 더해준 결과값을 리턴한다
  while (K가 요소를 가지고 있다면) {
    // K[0]을 빼내고, 그 값이 임의의 배열의 몇번째 인덱스인지를 찾아 기준점으로 잡는다
    let 기준점 = k[0]의 값을 K배열에서 빼오고, 이 값이 임의의 배열에서 몇번 인덱스인가를 찾음
    // 임의의 배열에서 기준점을 통해 K[0]과 같은 값을 제거해주고
    임의의 배열.splice(기준점, 1) // 기준점부터 1개의 값을 제거한다는 의미
    // 결과값에 남은 팩토리얼(K.length)를 기준점만큼 곱해준 값을 더해준다
    결과값 = 결과값 + 팩토리얼(K.length) * 기준점
    // 예를 들어, K[0]의 인덱스가 0이라면 1이라는 의미이고
    // 1의 경우에는 1을 기준점으로 하는 경우의 수가 처음 시작하는 경우의 수이므로
    // 2일 경우, 3일 경우....N일 경우의 수를 구할 필요가 없으므로
    // 처음 팩토리얼의 값에 0을 곱해 0으로 만들어 더해주는 것
  } // K에 요소가 남아 있다면 다시 while문으로 돌아가고, 다 빼서 계산했으면 나온다
  리턴 결과값 
}

4. 완성 코드

function orderOfPresentation (N, K) {
  function factorial(n) {
    if (n <= 1) {
      return n;
    } return n * factorial(n - 1);
  } 
  let mockArr = [];
  for (let i = 1; i <= N; i++) {
    mockArr.push(i);
  } 
  let result = 0;
  while (K.length > 0) {
    let set = mockArr.indexOf(K.shift());
    mockArr.splice(set, 1)
    result = result + factorial(K.length)*set;
  } 
  return result;
}