[JS] 2Level / 연습문제 / 줄 서는 방법

문제 설명

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

프로그래머스

 

문제 풀이 방법

이 문제는 순열 문제로 접근했다.

처음에는 직접 순열을 전부 구해 풀이를 진행했지만,

그렇게 하면 20! 만큼 구해야 되서 시간 초과가 발생했다.

 

그래서 참고한 글에서 주어진 k를 이용해 순서에 올 숫자를 구하는 방식을 이용한 풀이를 참고했다.

참고한 코드

const solution = (n, k) => {
    let arr = Array.from({length: n}, (_, i) => i+1);
    let answer = [];
    
    const func = (a) => {
        let fac = 1;
        for(let i=1; i<a.length; i++){
            fac *= i;
        }
        const idx = Math.ceil(k/fac) - 1;
        k = k - idx * fac;
        return arr.splice(idx, 1);
    }
    
    for(let i=1; i<=n; i++){
        const num = func(arr);
        answer.push(...num);
    }
    return answer;
}

 

코드를 약간 바꾸긴 했지만 뭔가 긴거 같다....

 

또 다른 방법으로 코드를 작성해 봤다.

const solution = (n, k) => {
    let arr = Array.from({length: n}, (_, i) => i+1);
    let answer = [];
    let fac = arr.reduce((acc, cur) => acc * cur, 1);
    
    while(answer.length < n){
        fac = fac / arr.length;
        answer.push(...arr.splice(Math.ceil(k / fac) - 1, 1));
        k = k % fac;
    }
    
    return answer;
}

 

결국 이 문제는 순열을 직접 구하지 않고 풀어야 되는 문제이다.

 

사람들의 번호를 갖는 배열 arr을 선언한 뒤, n!의 값을 구한 변수 fac을 선언해 준다.

 

fac는 결국 n * (n-1) * (n-2) * ... * 1 이다.

여기서 k라는 수는 처음 오는 수를 구하고 이후에도 다음에 어떤 수가 오는지 유추하는데 필요한 변수이다.

 

예시에서는 k가 5로 주어졌다.

이는 총 6개의 경우에서 5번째로 와야한다는 의미이다.

그렇다면 맨 처음에 올 수 있는 수의 경우는 3가지, 이는 fac이 3 * 2!이 된다는 것을 의미하고 2!마다 앞의 수가 변한다는 것을 알 수 있다.

 

그렇다면 처음 구한 fac(모든 경우)를 arr.length로 나눌 경우 ( fac / arr.length ) 만큼 앞의 숫자가 바뀐다는 것을 알 수 있다.

위의 코드에서 fac = fac / arr.length; 마다 앞의 수가 변경된다는 것을 알게되었다.

 

이제 앞의 수를 유추해봐야한다.

앞의 수는 Math.ceil(k / fac) - 1 로 구할 수 있다.

이는 fac 마다 앞의 수가 변경되는 것을 알고있을 것이다.

그렇다면 k 번째로 있을 조합에서 앞의 수가 몇번째에 있는 숫자인지 알 수 있다.

 

이렇게 앞에 있을 수를 구했다면 다음 수를 구하기 위해 k 는 k % fac으로 재할당 해주자.

이는 다음 구해야할 수가 앞의 수가 있는 경우 중에서 몇번째 인지 알아내기 위함이다.