[프로그래머스] Level2 - 줄 서는 방법(Javascript)

프로그래머스

▶ 문제 요약

1.  n명의 사람이 일렬로 줄을 서고 있다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있다. 

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

 

▶ 정답 코드

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

function solution(n, k) {
    let answer = [];
    // 숫자 배열
    let number = Array.from({length : n }, (_, i) => i+1);
    
    // n이 1보다 클때까지
    while (n > 0) {
        // 한 숫자를 고정하면 남은 숫자로 만들 수 있는 순열의 수 
        let fact = factorial(n-1);
        // k를 팩토리얼로 나눈 것을 올림하면 해당 인덱스 이후의 숫자를 선택하는데 적합
        let index = Math.ceil(k / fact) -1;
        
        // 현재 인덱스를 배열에 추가
        answer.push(number[index]);
        // 그리고 숫자배열에서 삭제
        number.splice(index, 1);
        
        // 3이 선택되면 1과 2로 시작하는 순열은 볼 필요가 없으니 삭제처리 
        k -= (fact * index);
        // n-1 해야 무한루프 탈출
        n -= 1;
    }
    return answer
}

▶ 풀이 과정

1. 팩토리얼 함수를 사용하는데 이유는 문제에서 n = 3이면 6가지 방법이 존재한다. 모든 순열의 수를 계산하는데 사용된다. 

 

2. n의 수만큼 배열을 만들어야한다. Array.from()메서드를 활용해서 만든다. ( _, i) 이 부분은 map함수와 비슷하다. 첫 번째 인자는 현재값이고, 뒤에 값은 인덱스이다. 근데 현재값은 없으므로 _ 이걸로 대신한다. 

 

3. while문을 이용해서 n이 0보다 클 때까지 동작하게 한다. 

 

4. 위에 팩토리얼 함수에 (n-1) 인자를 전달한다. 여기서 (n -1)인 이유는 예를 들어, [1, 2, 3]이 있다면 1을 첫 번째 항목으로 고정하면 남은 수는 [2, 3]이다. 그래서 (3-1)! = 2가 된다. 

 

5. k를 팩토리얼로 나눈 것을 Math.ceil() 함수를 사용하서 올림 처리했다. 왜 Math.ceil이라면 Math.ceil은 2.1이 나와도 3으로 올림하는데 Math.round()는 정확히 반으로 나눠지는 경우에만 올림을 해준다. 첫 번째 숫자를 선택할 떄, k를 n - 1 팩토리얼로 나눈 값이 정확히 나눠지지 않더라도 다음 번호로 넘어가야 한다. 그리고 -1을 하는 이유는 배열의 인덱싱이 0부터 시작하기 때문이다. 

 

6. 해당 인덱스를 배열에 추가하고 숫자 배열에 삭제한다. 

 

7. k -= (fact * index) 이 부분이 핵심이다. 예를 들어, k = 5 인 경우 우리는 앞 자리가 3인 배열을 찾아야한다. 그러면 1, 2로 시작하는 배열은 상관이 없고 쓸모가 없다. 따라서 우리가 찾는 k번째 순열을 업데이트하고 올바른 위치를 찾을 수 있다. 

 

8. n - 1은 루프를 탈출하기 위해서 사용한다.