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

1. 문제

문제 링크

설명
n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

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

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항

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

입출력 예

n	k	result
3	5	[3,1,2]

2. 풀이

주먹구구식

단순하게 재귀적으로 모든 나열하는 방법을 만들 다음,
그 중 k번째 방법을 택해도 정답을 만들 순 있습니다.
하지만, n은 최대 20까지 주어지고,
나열하는 모든 경우의 수는 n!, 즉 20!이 되어버리니 어림도 없습니다.

규칙 찾기

문제에서 나온 예시만 봐도 이미 규칙이 조금 보이지 않나요?
자 예시를 다시 봅시다.

• [1, 2, 3]
• [1, 3, 2]
  • 맨 앞의 숫자 1에 대해 2!의 경우의 수 존재
• [2, 1, 3]
• [2, 3, 1]
  • 맨 앞의 숫자 2에 대해 2!의 경우의 수 존재
• [3, 1, 2]
• [3, 2, 1]
  • 맨 앞의 숫자 3에 대해 2!의 경우의 수 존재

그렇습니다.
1번째 자리에 대해서 수 하나당 각각 나열하는 경우의 수는 (n - 1)!씩 있습니다.
이 (n - 1)!개의 각각의 경우가 n개가 있으니 (n - 1)! * n = n!이 되는 겁니다!
어디 이뿐인가요?
2번째 자리에 대해서 수 하나당 각각 나열하는 경우의 수는 (n - 2)!씩 있고,
이를 일반화를 하면 m번째 자리에 대해서 (n - m)!개의 경우의 수가 있다고 할 수 있습니다.

이제 이 규칙을 가지고 우리는 만들 경우의 수를 미리 뛰어넘을 수 있게 됩니다.

3. 전체 코드

function solution(n, k) {
    // 팩토리얼 배열 초기화 - 경우의 수를 뛰어넘기 위해 팩토리얼 배열을 만듭니다.
    const factorials = Array(n).fill(1);

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

    const ans = []; // 정답 배열
    const use = Array(n + 1).fill(); // 사용 여부

    // 정답에 추가하는 함수
    const addAns = (step) => {
        let count = 0; // 스텝만큼 건너 뛰었을 때의 숫자를 추가합니다.

        for (let i = 1; i <= n; i++) {
            if (!use[i] && ++count == step) {
                ans.push(i);
                use[i] = 1;
                return;
            }
        }
    };

    // 큰 팩토리얼의 수부터 뛰어넘어서 숫자를 만듭니다
    for (let i = n - 1; i >= 0; i--)  {
        // 팩토리얼의 숫자가 k보다 크다면 건너뛰지 않고 바로 앞의 숫자를 추가합니다.
        if (factorials[i] >= k) {
            addAns(1);
            continue;
        }

        // 건너뛸 스탭 계산
        const step = Math.ceil(k / factorials[i]);

        // 건너뛴 만큼 차감
        k -= Math.floor(k / factorials[i]) * factorials[i];
        
        // 이 때, 스탭 계산시, 딱 나뉘어 떨어졌을 때는 예외처리를 해줘야 합니다.
        // 나뉘어 떨어졌다는 의미는 해당 스탭의 마지막 숫자를 의미하기 때문에
        // 의도적으로 팩토리얼을 더해줘서 온전한 숫자를 만들게 합니다.
        k += k ? 0 : factorials[i];
        addAns(step);
    }

    return ans;
}

종이와 팬을 가지고 규칙을 찾아보면 충분히 풀 수 있는 문제였습니다.