[Programmers] 줄 서는 방법(JavaScript)

문제

요약

1부터 n번의 사람이 줄서는 방법을 사전순으로 나열했을 때, k번째 방법을 출력하시오.

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12936?language=javascript

---

풀이

런타임에러(시간초과)

1. permuations, combination 구현 방법 외우기!

function permutation(arr, num, k){
    const res = [];
    if(num === 1) return arr.map((v) => [v]);
    let cnt = 0;
    
    arr.forEach((v, idx, arr) => {
        cnt += 1;
        const rest = [...arr.slice(0,idx), ...arr.slice(idx+1)];
        const permutations = permutation(rest, num-1);
        const attach = permutations.map((p) => [v, ...p]);
        res.push(...attach);
        if (cnt == k) return res;
    })
    return res;
}

function solution(n, k) {
    const lst = Array.from({length: n}, (_, i) => i + 1)
    
    const result = permutation(lst, n, k);
    
    return result[k-1];
}

 

풀이2

 

시간초과 해결하는 방법은 떠오르지 않아서 다른 사람의 풀이를 참고 했다.

가장 이해가 잘 되었던 설명은 앞에서부터 하나씩 숫자를 정한다.

직접 손으로 풀어보면 이해가 쉽게 된다.

 

예를 들어, 1,2,3,4,5 인 리스트를 줄 세워 100번째 순서를 찾을 때,

맨 앞이 1이면, 1 ~ 24까지

맨 앞이 2이면, 25 ~ 48까지

맨 앞이 3이면, 49 ~ 72까지

맨 앞이 4이면, 73 ~ 96까지

맨 앞이 5이면, 97 ~ 120까지

이므로 100번째는 맨 앞이 5일 때에서 찾으면 된다.

리스트 길이-1의 팩토리얼로 k-1(인덱스는 0부터 세기 때문에)을 나눈 몫이 첫번째 자리의 숫자,

나머지가 다음 찾아야 할 값으로 생각하면 된다.

 

새로 알게된 것

1. reduce = map + sum 으로 이해하면 편하다. lst.reduce((ac, v) => ac * v, 1) --> 리스트에 있는 값들을 다 곱한다. ㅂ은 초기값

2. splice는 리스트의 idx위치에서 n개의 숫자를 제거해준다.

function solution(n, k) {
    let answer = [];
    const lst = Array.from({length: n}, (_, i) => i + 1)
    k--;
    
    while (lst.length){
        const fact = Array.from({length: lst.length-1}, (_, i) => i + 1).reduce((ac, v) => ac * v, 1);
        
        const idx = Math.floor(k / fact);
        k = k % fact;
        answer.push(lst[idx]);
        lst.splice(idx,1);
    }
    
    return answer;
}