문제

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 : 3
k : 5

출력

[3,1,2]

제한 사항

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

내가 했던 풀이 방법

첫 번째 자리에 올 수를 생각해보면 다음과 같이 각각 2가지씩 존재한다. 그렇다면 3번째에 올 방법은 첫 번째 자리가 2여야 할 것이다. 이를 첫 번째 자리부터 마지막 자리까지 생각해주는 방식으로 구현해주면 된다.

[1, *, *] => [1, 2, 3], [1, 3, 2] (2가지)
[2, *, *] => [2, 1, 3], [2, 3, 1] (2가지)
[3, *, *] => [3, 1, 2], [3, 2, 1] (2가지)

1. numbers에 1부터 n까지의 숫자를 저장해주고 답을 저장할 result 배열을 초기화해준다.
2. numbers에는 0번째 index부터 1번, 2번... 이 들어가있으므로 k번째는 k-1번째로 생각해야 하므로 remianing을 k-1로 초기화해준다.
3. i를 n부터 0보다 큰 수에서 다음 내용을 반복해준다. (i-1)!을 구해주고, 해당 값을 remaining과 나눠준 몫을 cal에 저장해주고, numbers의 cal번째의 수를 result에 저장해준다.
4. numbers에서 방금 저장된 수를 삭제해준 다음 remaining을 fact으로 나눈 나머지로 덮어쓰기 해준다.
5. 3~4번을 반복한 뒤에 result에 들어있는 값이 k번째 방법이 된다.

코드

function solution(n, k) {
    function factorial(num) {
        let result = 1;
        for (let i = 2; i <= num; i++) {
            result *= i;
        }
        return result;
    };
    
    let numbers = Array.from({ length: n }, (_, i) => i + 1);
    let result = [];
    let remaining = k - 1;
    
    for(let i=n; i>0; i--) {
        let fact = factorial(i-1);
        let cal = Math.floor(remaining/fact);
        result.push(numbers[cal]);
        numbers.splice(cal, 1);
        remaining %= fact;
    }
    
    return result;
}

회고

DFS 문제로 생각해서 DFS로 풀었다가 시간초과가 났는데 도저히 모르겠어서 다른 사람 풀이를 참고했다. 풀이 방법이 어려운 건 아닌데 이런걸 어떻게 생각할 수 있는지가 참 궁금하다... 실버1, Lv2 정답률 낮은 문제들을 풀기 시작하면서 스스로 풀기 어려워지는 문제가 많은 것 같다. 이런 풀이들에도 익숙해져야겠다.. 무조건 다양하게 풀어보는 게 최선이겠지...?