🔎 줄 서는 방법

❓ 문제링크

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

📄 제출 코드

function solution(n, k) {
    let answer = [];
    let people = [];
    for (let i = 1; i <= n; i++) {
        people.push(i);
    }
    let all = factorial(n);
    k--; // k번째 idx
    for (let i = 0; i < n; i++) {
        all /= n - i; // (n-1)!
        let idx = Math.floor(k / all);
        answer.push(people[idx]);
        people.splice(idx, 1);
        k %= all;
    }
    return answer
}
function factorial(n) {
    let num = 1;
    for (let i = 1; i <= n; i++) {
        num *= i
    }
    return num;
}

let n = 3;
let k = 5;
console.log(solution(n, k));

처음에는 간단한 수열문제라고 생각했다.
people에 1부터 n까지 숫자를 채우고, people로 n명 줄서는 방법의 순열을 구해서 k번째 사람을 구하는 방법으로 구현했다.
그러나 효율성에서 시간초과가 났다.

다른 방법이 있나? 하고 고민하다가 질문게시판에 들어가보니 전체 수열을 다 만들지말고, 특정위치의 수열을 찾는 방법을 구해 봐라. 나열하다보면 규칙이 보인다. 라고 댓글을 보았다.
처음엔 안보였는데 문제를 다시보다가 k는 n!이하 자연수라는게 보여서 힌트를 얻었다.
굳이 왜 n!이라 썻을까 하고 나열한걸 다시보니 n!이 보였다.

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

1 1		1가지	1
1  

2 2		2가지	1*2
1 2
2 1

3 5		6가지	1*2*3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

한개당 그전꺼 n-1!개

4 5		24가지	1*2*3*4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1 
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

n=4, k=5인 경우
people = [1, 2, 3, 4]
all = 24 /= 4 >> 6

idx = 5/6 = 0 >>>>>>>>1
k = 4 % 6 = 4

people = [2, 3, 4]
all = 6 /= 4-1 >> 2
idx = 4 / 2 = 2>>>>>> 4
k = 4 % 2 = 0

people = [2, 3]
all = 2 /= 2 >> 1
idx = 5 / 1 = 0 >>>>>> 3
k = 0 % 1 = 0 

people = [2]
all = 1 /= 1 = 1
idx = 5 / 1 = 0 >>>>>> 2
k = 0 % 1 = 0

answer = [1, 4, 3, 2]

처음에 아이디어를 생각하고, 구현하는데 규칙을 식으로 표현하려는게 잘되지않아 다른분의 코드를 참고하였다.

📘 참고

https://velog.io/@johnyejin/JavaScript-프로그래머스-줄-서는-방법-LEVEL3