[programmers/py,js] 줄 서는 방법

줄 서는 방법

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

문제 설명

n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다.

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

제한사항

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

풀이 설명

factorial을 이용해 현재 index를 뽑아내는 방식으로 접근

import math

def solution(n, k):
    arr = [i for i in range(1, n+1)]
    answer = []
    
    while arr:
        v = (k-1) // math.factorial(n-1)
        answer.append(arr.pop(v))
        
        k = k % math.factorial(n-1)
        n -= 1
            
    return answer

• JS 풀이

문제의 예시로 보면 n=3, k=5 list=[1,2,3]
list를 통해 가질 수 있는 총 방법(f)은 3! = 6가지입니다.

좀 더 자세히 보면 밑과 같은 경우의 합 입니다.
1부터 시작하는 경우 2가지(6/n) =  2!
2부터 시작하는 경우 2가지(6/n)
3부터 시작하는 경우 2가지(6/n)

k - 1을 하는 이유? 우리가 구할 index는 0부터 시작

전제적인 변화를 작성해 보면
3 : n = 3, k = 4, f = 2, list = [1,2,3]
1 : n = 2, k = 0, f = 1, list = [1,2]
2 : n = 1, k = 0, f = 1, list = [2]
과 같은 순서로 값의 변화가 진행되야 합니다.

이를 통해 우리가 원하는 번호 k번재 방법의 첫 인덱스를 구하면
list[2] = list[Math.trunc(k / (f/n))]임을 알 수 있습니다.
그리고 list에서 3을 제거합니다.
k %= f, n -= 1 과정을 반복하면 값을 구할 수 있다.

function solution(n, k) {
    let list = Array(n).fill(0).map((_, i) => i + 1);
    const answer = [];
    let f = list.reduce((a, c) => a * c, 1);
    k -= 1;
    
    while (list.length) {
        f /= n;
        const idx = Math.trunc(k / f);
        answer.push(list[idx]);
        list = list.filter((_, i) => i !== idx);
        
        k %= f;
        n -= 1;
    }
    
    return answer;
}