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

# 문제 원문

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]

 

# 문제 풀이

처음에는 순열을 모두 구한후 k-1번째 배열을 구할려고 했으나 정확성 13번 배열길이 초과 와 효율성 모두 시간초과로 실패하는 걸 보고 DP로 선회 했다. 먼저 팩토리얼을 통해서 순열의 모든 경우의 수를 구하고, 그 경우의 수에서 idx를 구해서 그 idx에 해당하는 요소를 result에 하나씩 삽입해주면 되는 문제이다. 풀이 자체는 크게 어렵지 않지만 규칙을 찾는게 어렵다. 나는 팁을 보고 도움을 받았다.

 

# 솔루션 플로우

1. 입력 받은 n의 길이에 맞는 1~n까지의 원소를 가진 1차원 배열 arr를 구한다.

2. 구해진 arr의 각 요소를 1과 곱해서 해당 배열의 모든 경우의 수 fact를 구한다.(팩토리얼)

3. arr의 idx는 0 부터 시작하므로 k에서 1을 빼준다.

4. arr가 빈배열이 될때 까지 반복한다.

5. fact를 arr.length로 나눈후 k를 fact로 나누어서 arr의 idx를 구하고 k를 다시 fact로 나눈 나머지로 구한다.

6. arr배열에서 구해진 idx에 맞는 요소를 빼서 result에 넣어준다.

7. 구해진 result를 반환한다.

1. DP

function solution(n, k) {
    const result = [];
    const arr = new Array(n)
        .fill(true)
        .map((_, idx) => idx + 1);
    let fact = arr.reduce((result, current) => result * current, 1);

    k--;
    while(arr.length > 0){
        fact /= arr.length;
        const idx = Math.floor(k / fact);
        k %= fact;

        result.push(arr.splice(idx, 1)[0]);
    }

    return result;
}