[JavaScript] toy 01 orderOfPresentation

문제

말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.

선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.

김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.

총 조의 수 N과 선생님이 말씀하시는 발표 순서 k가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.

모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다.
ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

입력

인자 1:N

• Number 타입의 1 <= N <= 12인 조의 개수

인자 2: K

• Number 타입의 Array (0 <= index)

ex) n이 3이고 k가 [2, 3, 1]일 경우
모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,
반환하는 값은 3이 됩니다.

주의사항

• k내에 중복되는 요소는 없다고 가정합니다.

입출력 예시

let output = orderOfPresentation(3, [2, 3, 1]);
console.log(output); // 3

output = orderOfPresentation(5, [1, 3, 2, 4, 5])
console.log(output); // 6

풀이

잘못된 접근 방법

처음에 봤을 땐 ‘순열(permutation)’을 구해서 몇 번째인지 구하나…? 라는 생각을 했었다.
그러나 실제로 순열 코드를 구현했던 글을 참고해서

1. 1부터 N까지의 숫자로 만들 수 있는 N!개의 순열 집합 나열하기.
2. for문으로 K와 같은 조합을 찾기.
3. 찾은 조합이 몇 번째인지 구해서 return하기.
   위의 방법대로 풀어 보아도 테스트를 돌리면 에러가 날 뿐이었다 ㅠㅠ 분명 뭔가 문제가 된 거겠지…

후에 답안의 설명을 읽어봤더니 일반적인 수행 속도 상한아 약 1억인데, 이 문제의 입력 인자 N은 최대 12이므로 12!(순열 경우의 수)이 1억이 넘어서 안 되는 거라고 한다…ㅠㅠ

로직

순열을 죄다 구하는 방식이 아닌, 최소한으로 구할 수 있도록 로직을 짜야 한다.
만약 입출력 예시처럼 N이 3, K가 [2,3,1]일 때를 생각해 보자.
K의 첫 번째 수가 2로 시작하는 걸 알고 있으니, 최소 1로 시작하는 순열(1ㅁㅁ) 수보단 return해야 하는 order수가 더 큰 것을 확인할 수 있다.
바로 이 점을 이용하는 것이다.
1로 시작하는 경우의 수는 2가지이다.(=2*1) (=A)
이후 K의 두 번째 수가 3이니, 21ㅁ 형태의 경우의 수는 다 체크한 뒤의 order수라고 할 수 있다.
그렇다면 1. (=B)
이후 K의 마지막 수는 1이니, 1보다 앞선 숫자가 들어갈 경우를 구해야 하지만, 없다!
그래서 답은 3이 된다.

위 경우대로라면 수도 코드는 다음과 같게 된다.

1. 순열의 경우의 수를 구하는 함수를 작성한다. = factorial
2. for문으로 K의 요소들을 훑어보되, 그때마다 ‘이 숫자(조 순번)를 썼습니다’를 가리킬 false 배열을 만들어둔다. 단 0조는 없으므로 index를 고려하여 N+1 length만큼의 배열이어야 한다. false는 truefh 바뀔 건데, 위 예시에서 K의 첫 번째 요소가 2니까 두 번째 false가 true로 바뀔 것이다.(=[false(0번째 더미),false,false,false] => [false(0번째 더미),false,true,false]) = Array(N+1).fill(false);
3. A를 구하기 위해 i번째 요소(예시 기준으로 첫 번째 수 = 2)보다 앞선 숫자가 쓰였는지 확인하고(false?), 그를 이용한 순열의 경우의 수를 구한다.
4. 3번에서 구한 수를 추후 return할 order 변수에 추가한다.
5. 이후 K의 두 번째, 세 번째 수를 훑으며 order을 최종적으로 return한다.

기술 코드

// 순열의 가짓수를 구하는 방법은 factorial이므로,
// for문으로 쭉 곱하거나, 재귀함수를 이용할 수 있다.

// for문일 경우
const factorial = (n) => {
  let result=1; // 1! = 1
  for(let i = 1; i < n + 1; i++){
    result = result * i;
  }
  return result;
}

// 재귀함수일 경우
const factorial = (n) => {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

해답 코드

function orderOfPresentation (N, K) {
  // factorial 함수를 만들어둡니다.
  const factorial = (n) => {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
  };

  // 추후 return할 발표 순서를 선언/할당합니다.
  let order = 0;
  
  // N개의 조 중에, '이 숫자(조 순번)를 썼습니다'를 가리킬 false 배열을 만들어 둡니다.
  // 만약 N이 3이라면 [false(0조는 없으므로 더미), false, false, false]로 생성됩니다.
  const isUsed = Array(N + 1).fill(false); // index값을 고려하여 N+1로 둡니다.
  
  // K 내부를 for문으로 훑습니다.
  for (let i = 0; i < K.length; i++) {
    // K의 i번째 조를 num 변수에 선언/할당시킵니다.
    let num = K[i];

    // 사용여부 판별을 위해 isUsed에 true로 바꿔둡니다.
    // 이는 조를 중복 사용하지 않기에 사용하는 로직입니다.
    isUsed[num] = true;

    // num보다 앞에 올 수 있는 수들의 배열을 복제해서 사용하지 않은 수를 구하고,
    // factorial로 경우의 수를 구한 뒤 order에 카운트합니다.('로직' 파트의 A 같은 상황)
    let candidates = isUsed.slice(1, num);
    let validCnt = candidates.filter((el) => el === false).length;

    // i는 0부터 시작하기 때문에 N에서 남아 있는 수를 구할 때 '- 1'이 추가로 필요합니다.
    const formerCnt = validCnt * factorial(N - i - 1); 
    
    // return할 order에 추가합니다.
    order = order + formerCnt;
  }

  return order;
}

카카오페이로 커피사기 ❤️ 토스 계좌로 커피사기 ❤️