[프로그래머스 lev2/JS] 줄 서는 방법

문제 출처

프로그래머스 lev2 - 줄 서는 방법

나의 풀이

1차 시도 (정확성 통과, 효율성 실패)

재귀는 시간초과가 발생한다.

function solution(n, k) {
  let ch = Array.from({length:n}, () => 0);
  let tmp = [];
  let answer;
  let cnt = 0;
  function dfs(L) {
    if (cnt>k) return;
    if (L>=n) {
      cnt++;
      if (cnt===k) answer = tmp.slice();
    }
    else {
      for(let i=0; i<n; i++) {
        if (ch[i]===0) {
          ch[i]=1;
          tmp[L]=i+1;
          dfs(L+1);
          ch[i]=0;
          tmp.pop();
        }
      }
    }
  }
  dfs(0);
  return answer;
}

console.log(solution(3, 5));

2차 시도 (통과)

// 1.
예를 들어 n이 4일 때
각 숫자에 대한 선택 경우의 수를 생각해보면,
첫번째 자리에 들어갈 숫자는 4개중 1개이다. 이걸 거꾸로 생각하면 4개중에서 3개를 선택하면 자동으로 첫번째 자리 숫자는 결정된다. (4C3)
두번째 자리에 들어갈 숫자는 3개 중 1개인데, 마찬가지로 3개 중에서 2개를 선택하면 자동으로 두번째 자리 숫자가 결정된다. (3C2)
...
nCn-1은 결국 팩토리얼 n!을 의미한다(서로 다른 n개 나열)

각 자리에 대한 경우의 수를 Factorial() 함수로 구해서 ar 배열에 넣는다. ar = [n!, (n-1)!, ..., 1]
동시에 person 배열에 1부터 n까지 넣는다.

// 2.
ar 배열에 대해 for문을 순회한다.

예를 들어
ar[0]==24일 때,
1,2,3,4가 각각 6(arr[0]/사용 가능한 숫자 개수)가지 경우의 수를 가진다.
cloneK==5이면 6보다 작으므로 첫번째 자리에는 1이 들어가야 한다.
이때 0보다 크고 6보다 작으므로 cloneK에서 0을 빼준다.

arr[1]==6일 때,
2,3,4는 각각 2(arr[1]/사용 가능한 숫자 개수)가지 경우의 수를 갖는다.
cloneK==5면 4보다 크고 6보다 작으므로 남은 숫자 중에서 3번째로 큰 숫자 4가 두번째 자리에 들어가야 한다. 그리고 cloneK에서 4를 빼준다.
...

function Permutation(nn,rr) {
  let n = 1, r = 1;
  for(let i=2; i<=nn; i++) n *= i;
  for (let i=2; i<=(nn-rr); i++) r *= i;
  return n/r;
}

function solution(n, k) {
  let answer = [];
  let person = [];
  let ar = [];
  // 1. 
  for (let i=n; i>=1; i--) {
    ar.push(Permutation(i,i-1));
    person.unshift(i);
  }
  // 2. 
  let cloneN = n, cloneK = k;
  for (let i=0; i<ar.length; i++) {
    let j=1;
    let select = (ar[i]/cloneN) * j;
    while (select<cloneK) {
      j++;
      select = (ar[i]/cloneN) * j;
    }
    cloneK = cloneK - (ar[i]/cloneN) * (j-1); 
    answer.push(...person.splice(j-1, 1));

    cloneN--;
  }
  return answer;
}
console.log(solution(4, 5));