[Programmers] 줄 서는 방법(JavaScript)

 

알림

 

본 포스팅은 공부 목적으로 작성된 글이며 상업적 목적으로 절대 사용되지 않았음을 밝힙니다.

 

문제

 

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

프로그래머스

 

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 함수를 완성해주세요.

 

코드

 

function solution(n, k) {
    let answer = [];
    // [1, 2, 3, ..., n] 형태의 배열 생성
    let arr = new Array(n).fill(1);
    for(let i = 1; i < n; i++) arr[i] = arr[i-1] + 1
    let idxK = k-1; // 실제 k번째는 배열 인덱스에서는 -1 위치
    
    while(arr.length){
        // 나눠 떨어진다면,
        if(idxK === 0){
            answer.push(...arr);
            break;
        }
        
        let fact = factorial(arr.length - 1); // 받아온 n - 1의 팩토리얼
        let idx = Math.floor(idxK / fact) // 소수점 버림, 정수 반환
        
        idxK = idxK % fact
        
        answer.push(arr[idx]);
        arr.splice(idx, 1);
    }
    
    return answer;
}

// 팩토리얼 함수
function factorial(n){
    let res = 1;
    for(let i = 2; i <= n; i++) res *= i;
    return res;
}

 

풀이

 

n이 3이라면, [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 이처럼 배열이 들어올 것입니다.
그리고 보시다시피 배열의 첫 번째가 두 번마다 바뀌는 것을 확인할 수 있습니다.

즉, n이 3일 때, n-1의 팩토리얼마다 바뀌는 것이죠.(n이 4라면, 3!인, 6번째마다 배열의 첫 번째 요소가 바뀔 것입니다.)

그리고 n=3일 때, k가 2라면? 배열의 첫 번째 1로 시작합니다. 즉, k/n-1 = 2/2 = 1입니다.
마찬가지로 k가 4라면? 배열의 첫 번째 2로 시작합니다. k/n-1 = 4/2 = 2입니다.
마지막으로 k가 6이라면? 배열의 첫 번째 3로 시작하고, k/n-1 = 6/2 = 3입니다.

 

이처럼 주어진 자연수 k를 n-1로 나눴을 때, 해당 몫은 맨 앞에 위치한 요소의 인덱스인 것입니다.
하지만 여기서 k번째는, 배열에서는 k-1번째이기 때문에, k-1/n-1로 구해야 합니다.

해당 문제는 위에서 설명한 내용과 해당 내용을 수행하기 위한 팩토리얼을 실행해줄 함수를 만들어 풀이하시는 것이 포인트입니다.

 

그 외 자세한 내용은 여기를 클릭해서 학습해 주시기 바랍니다. 해당 문제를 포스팅 하신 한 개발자의 velog입니다.

저도 해당 velog를 많이 참고하여 문제 해결에 많은 도움을 받았습니다.