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

문제

줄 서는 방법

https://school.programmers.co.kr/learn/courses/30/lessons/12936

 

 

예시 코드

function solution(n, k) {
  const answer = [];
  const numbers = Array.from({ length: n }, (_, i) => i + 1);
  k--; // 0-based indexing

  while (n > 0) {
    const factorial = factorials(n - 1);
    const index = Math.floor(k / factorial);
    answer.push(numbers[index]);
    numbers.splice(index, 1);
    k %= factorial;
    n--;
  }

  return answer;
}

function factorials(num) {
  let result = 1;
  for (let i = 2; i <= num; i++) {
    result *= i;
  }
  return result;
}

 

풀이

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열하는 방법을 사전 순으로 나열했을 때, k번째 방법을 구하는 문제입니다.

 

기본 개념

n명의 사람을 줄 세우는 방법의 수는 n!입니다.

n! = n * (n-1) * (n-2) * ... * 1

 

만약 첫 번째 번호가 정해졌다면, 나머지 번호로 만들 수 있는 가짓수는 첫 번째 번호를 제외한 (n-1)! 이 됩니다.

마찬가지로 두 번째 번호까지 정해졌다면, (n-2)!가 되겠죠.

예를 들어, n = 5인 경우, 5! = 120가지의 방법으로 줄을 세울 수 있습니다.
사전 순으로 나열하므로, 첫 번째 방법은 [1, 2, 3, 4, 5]이고, 마지막인 120번째 방법은 [5, 4, 3, 2, 1]이 됩니다.

 

첫 번째 번호가 1인 경우, 나머지 번호로 만들 수 있는 가짓수는 4! = 24입니다.

즉, 첫 번째 번호가 1일 때 1번부터 24번까지의 방법을 만들 수 있습니다.

[1, 2, 3, 4, 5], [1, 2, 3, 5, 4], ... , [1, 5, 4, 3, 2]

 

마찬가지로 첫 번째 번호가 2인 경우, 25번부터 48번까지의 방법을 만들 수 있습니다.

 

첫 번째 번호가 1, 두 번째 번호가 2인 경우, 나머지 번호로 만들 수 있는 가짓수는 3! = 6입니다.

1번부터 6번까지의 방법을 만들 수 있습니다.

[1, 2, 3, 4, 5], [1, 2, 3, 5, 4], ... , [1, 2, 5, 4, 3]

 

첫 번째 번호가 1, 두 번째 번호가 3인 경우, 7번부터 12번까지의 방법을 만들 수 있습니다.

 

코드 설명

기본 개념에서 설명한 방식대로,  k에 따라서 앞 자리부터 하나씩 숫자를 정해나가면 됩니다.

 

먼저 0-based indexing을 위해 k값을 1 감소시킵니다.

 

루프 진행

첫 번째 번호를 제외한 나머지 번호로 만들 수 있는 가짓수를 구합니다.

const factorial = factorials(n - 1);

 

첫 번째 번호를 구해서, 정답 배열에 집어넣습니다.

const index = Math.floor(k / factorial);
answer.push(numbers[index]);

 

사용된 번호를 제거합니다. k와 n 값을 갱신합니다.

numbers.splice(index, 1);
k %= factorial;
n--;

 

전체 시간 복잡도는 O(n^2)입니다.

 

테스트

n = 5, k= 53인 경우,

각 루프마다 각 변수 값은 다음과 같이 변화합니다.

 

n	5	4	3	2	1
k	52	4	4	0	0
factorial	24	6	2	1	1
index	2	0	2	0	0
numbers	[ 1, 2, 3, 4, 5 ]	[ 1, 2, 4, 5 ]	[ 2, 4, 5 ]	[ 2, 4 ]	[ 4 ]
answer	[ 3 ]	[ 3, 1 ]	[ 3, 1, 5 ]	[ 3, 1, 5, 2 ]	[ 3, 1, 5, 2, 4 ]