[CodeKata] 프로그래머스(Lv3) : 줄 서는 방법

🥋 Oooth More!! (Level 3) 

 

 

 

🧮 풀이

- 풀이1 : 순열(permutation)

우선 가장 직관적으로, 순열을 통해 줄 설 수 있는 모든 방법을 구한 다음에 k번째를 반환해보았다.

풀이가 틀리진 않았으나, 아마 모든 순열 케이스를 구해야 하기 때문에 n이 커지는 경우(일부 테스트 케이스, 효율성 테스트)에 런타임 에러가 발생한 것 같다.

function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    const restArr = arr.filter((_, index) => index !== idx);
    const permuationArr = permutation(restArr, selectNum - 1);
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
}

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

1. permutation() 순열 함수

• permutation()은 배열의 순열들을 구하는 함수로, 인자는 arr(원배열), selectNum(요소개수) 2가지를 받는다.
• selectNum이 1개인 경우는 arr 각 요소를 배열로 가진 이중배열을 반환한다. (또한, permutation 재귀가 끝나는 지점)
• 아닌 경우엔, permutation() 함수의 DFS를 통해 순열을 구한다. arr를 순회하며, fixer는 현재값(v)을 저장해놓은 변수, restArr은 현재값을 제외한 나머지 값들의 배열이다.
• permutationArr은 permutation()에 restArr과 (selectNum - 1)을 전달하며 fixer를 제외한 나머지 값들의 순열 케이스들을 계속해서 구해나간다.
• 배열의 길이가 긴 것부터 재귀가 시작됬지만, 길이가 1인 배열부터 permutation() 연산이 끝난다. 이렇게 저장된 permutationArr 케이스들에 fixer를 더한 combineFixer 케이스들을 생성해준다. 이것이 하나의 값을 고정한(fixer) 현재 개수(selectNum)의 모든 순열 케이스인 것이다.
• 마지막으로, result에 이 combineFixer들을 더하면, 현재 개수(selectNum)의 모든 순열조합이 result에 담긴다.

 

2. solution() 정답 계산

• nums는 1부터 n까지 정수들의 배열이다. Array.from()을 사용했으며, i가 0부터 시작하기에 1을 더한 것이다.
• permutation()에 (nums, n)를인자로 넘기면, [1, 2, ...n]의 모든 순열 케이스 배열이 나온다. 이것의 k-1번째 인덱스를 반환한다.

 

 

​- 풀이2 : 나눗셈과 factorial

모든 순열을 구하지 않더라도, k번째에 해당하는 값만 nums에서 검출할 수 있을지 고민해보았다.

 

n이 4인 경우를 가정하자. 1~6번째는 [1, ...], 7~12번째는 [2, ...], 13~18번째는 [3, ...], 19~24번째는 [4, ...] 의 규칙성을 보인다.

이 때, 6은 n-1까지의 곱, 즉 (n-1)! 팩토리얼이다.

 

또한, 1~6번째 안에서, 1~2번째는 [1, 2, ...], 3~4번째는 [1, 3, ...], 5~6번째는 [1, 4, ...] 의 규칙성을 다시 보인다.

여기서도, 2는 n-2까지의 곱, 즉 (n-2)! 팩토리얼이다.

 

이러한 규칙성에 의거, 팩토리얼로 k를 나눈 몫을 통해 nums의 요소를, 나머지는 다시 k로 갱신하는 방법이 가능할 것 같다 생각했다.

 

const factorial = (n) => Array.from({ length: n }, (_,i) => i+1).reduce((acc,cur) => acc * cur);

function solution(n, k) {
  let answer = [];
  const nums = Array.from({ length: n }, (_,i) => i+1)
  
  for (let i = n-1 ; i > 0 ; i--) {
    const q = Math.ceil(k / factorial(i));
    answer.push(nums.splice(q-1, 1)[0])
    const r = k % factorial(i);
    k = r
  }
  
  answer.push(nums[0])
  
  return answer
}

 

• factorial() 은 1~n의 곱을 구하는 팩토리얼 함수다. [1, 2, ...n] 배열을 만든 뒤, 이를 reduce()로 곱해줬다.
• answer은 정답을 누적할 배열, nums는 위 풀이와 동일하게 사람수 n을 [1, 2, ...n] 으로 가공한 배열이다.
• (n-1)부터 1씩 줄어들며 계산을 한다. 먼저, q는 k를 factorial(i)로 나눈 값을 올림(ceil)한 값이다. n = 3인 경우, floor(내림)은 [0,1,1,2,2,3], ceil(올림)은 [1,1,2,2,3,3]으로 나온다. (k가 인덱스가 아닌 몇번째를 의미하기 때문)
• nums[q-1] 값이 위에 서술한 규칙성에 해당하는 값이다. 이를 nums에서 splice()로 뺀 다음, answer에 넣어준다.
• r은 k를 factorial(i)로 나눈 나머지이다. 이를 k로 갱신하면, 남은 nums들 중 다음에 올 요소를 계산할 수 있다.
• 모든 연산이 끝나면, nums에는 선택되지 않은 1개의 값만 남아있다. 이를 맨 마지막에 answer에 push() 한 뒤, 정답을 반환한다.

 

 

 

🖇 리뷰

모범답안의 원리가 내 풀이와 유사하여 별도로 가져오진 않았다.

순열의 비효율성을 짚으면서 해당 순번의 케이스만 뽑을수 있는 방법을 고민하였고, 특정 규칙성과 여기에 쓰이는 값이 팩토리얼이라는 것을 인지하니 생각보다 어렵진 않은 문제였다.