[Javascript] 줄 서는 방법 (12936)

문제링크

코딩테스트 연습 - 줄 서는 방법

 

접근 방법

기본적으로는 순열 방식을 사용해 모든 경우의 수를 구하고 k번째를 구할 수 있지만
아마 효율성에서 떨어질 것 이다.

순열의 규칙을 파악하여 특정 index의 순열을 구해야한다.

[1,2,3,4] 배열의 순열로 규칙을 파악해 보겠다. 총 4!의 순열이 나오고 (3!) * 4 개로 나눌 수 있다.
0번 인덱스의 값은 아래 처럼 나온다.
0~5     => 0
6~11   => 1
12~17 => 2
18~23 => 3
즉 (n-1)! 로 나눈 몫을 순열의 기본형 [1,2,3,4]의 index로 주어 0번 index의 값을 얻을 수 있다.

말로 설명하려니 참 어렵다.. 쉽게 생각하면

k / (n-1)! 로 현재 값의 index를 얻고
k % (n-1)! 로 다음 값의 index 값을 얻을 수 있다. (여기서 index란 기본형 [1, 2, 3, 4..n-1, n]의 index를 의미 )
만약 k % (n-1)! === 0이라면 기본형의 남은 배열을 그대로 추가해주면 된다.

코드를 살펴보면

1. 먼저 배열의 기본형 (1 ~ n까지 오름차순으로 정렬된 배열)을 만들어 준다.

const base = Array.from({ length: n }, (_, i) => i + 1);​

2. 순열의 모든 경우의 수는 0~(n! - 1)까지 이므로 k -= 1을 해준다.

3. 종료 조건 ( k === 0) 을 만들어준다. ( k % (n-1)! === 0 인 경우 남은 base의 요소를 모두 push )

if (k === 0) {
  answer.push(...base);
  break;
}​

4. 앞서 말했듯이 k / (n-1)! 는 현재 위치의 값의 index이고, k % (n-1)!는 다음 위치를 구하기 위한 값이다.

while (true) {
    n--;
    
    const index = Math.floor(k / factorial(n));
    k = k % factorial(n);
    answer.push(base[index]);
    base.splice(index, 1);
}​

( 주의점, base[index]를 사용하고 나서 해당 값을 지워줘야 한다. )
 => [1,2,3,4]에서 index 2를 사용하고나면 [1,2,4]로 업데이트

 

function solution(n, k) {
  const base = Array.from({ length: n }, (_, i) => i + 1);
  var answer = [];
  k -= 1;

  while (true) {
    n--;
    if (k === 0) {
      answer.push(...base);
      break;
    }
    const index = Math.floor(k / factorial(n));
    k = k % factorial(n);
    answer.push(base[index]);
    base.splice(index, 1);
  }

  return answer;
}

const factorial = (num) => {
  if (num === 0) return 1;
  return num * factorial(num - 1);
};