프로그래머스 LV2 질문목록

문제

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

프로그래머스

답

//1,2,3,4
function solution(n, k) {
    function permutate (arr,x) {
        const result = []
        if (x === 1) {
            return arr.map(e=>[e])
        }
        arr.forEach((fixed,index,origin) =>{
            const sub = [...arr.slice(0,index),...arr.slice(index+1)]
            const permutation = permutate(sub,x-1)
            const plus = permutation.map(e=>[...e,fixed])
            result.push(...plus)
        })
        return result
    }
    const arr = Array.from({length:n},(_,i)=>i+1)
    const li = permutate(arr,n).sort((a,b)=>Number(a.join(""))-Number(b.join("")))
    return li[k-1]
    
}

처음에 순열로 만든다음 정렬하여 나타낼려고 했으나 런타임 에러가 떴었다.

그래서 찾아보니

const solution = (n, k) => {
        const result = []; // 결과값
        const arr = new Array(n).fill(1).map((_, i) => _ + i); // n = 3, arr = [1, 2, 3]

        function getNum(arr) { // k에 해당하는 순열의 원소를 하나씩 구하기 위한 함수.
          let fac = 1;
          for (let i = 1; i < arr.length; i++) {
            fac *= i;
          }
          // fac => (n - 1)!, fac개씩 앞자리 숫자가 변함.

          const idx = Math.ceil(k / fac) - 1;
          // k = 1, 2 => idx = 0, k = 3, 4 => idx = 1, k = 5, 6 => idx = 2
          // ex) n = 3, k = 5, idx = Math.ceil(5 / 2) - 1 = 3 - 1 = 2

          k = k - idx * fac;
          // idx를 구한 뒤 다음 루프 연산을 위해 k값을 갱신.
          // ex) k = 5, idx = 2, k = 5 - (2 * 2!) = 1  

          return arr[idx];
          // 배열 idx에 해당하는 원소를 return.
        }

        for (let i = 1; i <= n; i++) { // loop문 한번에 하나씩 원소를 넣으므로 총 n번 반복.
          const num = getNum(arr); // n개의 숫자 배열에서 연산을 통해 원소 하나씩 구함.
          arr.splice(arr.indexOf(num), 1); // 꺼낸 숫자를 원래 배열에서 제거.
          result.push(num); // 결과값 배열에 꺼낸 숫자를 push.
        }

        return result;
      };

순서k에 따라 찾아야 하는 답의 배열의 인덱스 자리를 각각 유추할 수 있는 방법이 있다.

매우 신기했고 이런 순열문제가 나오면 이 방법을 이용해야 할 것 같다