[Javascript] 프로그래머스 - 줄 서는 방법

문제 설명

n명의 사람이 일렬로 줄을 설 때, 이들을 나열하는 모든 경우를 사전 순으로 나열했을 때, k번째 순열을 구하는 문제입니다.
예를 들어, n이 3일 경우 가능한 순열은 다음과 같습니다:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

이 중에서 k번째 순열을 반환해야 합니다.

---

제한 사항

• n은 1 이상 20 이하의 자연수입니다.
• k는 n! 이하의 자연수입니다.

---

해결 방법

• 알고리즘: 순열과 팩토리얼을 활용한 탐욕적 선택
  1. 팩토리얼 계산: 각 숫자의 자리수를 결정하기 위해 1부터 n까지의 팩토리얼을 미리 계산합니다.
  2. k를 활용한 인덱스 계산: k를 기준으로 현재 선택해야 할 숫자의 인덱스를 결정합니다. 이는 k ÷ (n-1)!로 구합니다.
  3. 숫자 선택 및 제거: 계산된 인덱스에 해당하는 숫자를 결과 배열에 추가하고, 사용한 숫자를 제거합니다.
  4. 반복: 남은 숫자와 줄어든 k값을 기준으로 위 과정을 반복합니다.

---

시간 복잡도

• 팩토리얼 계산: O(n)
• 순열 생성 과정: O(n²)
  각 자리에서 가능한 숫자를 선택하고, 배열에서 해당 숫자를 제거하는 데 O(n)의 시간이 필요하며, 이를 n번 반복합니다.

---

구현 코드

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

  for (let i = 1; i <= n; i++) {
    factorials[i] = factorials[i - 1] * i;
  }

  let num = k - 1;

  for (let i = n; i > 0; i--) {
    const index = Math.floor(num / factorials[i - 1]);
    num %= factorials[i - 1];
    answer.push(arr[index]);
    arr.splice(index, 1);
  }

  return answer;
}