Toy 1 짱구는 못말려

woobaeh·2022년 3월 2일

Algorithm

목록 보기

2/7

문제

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

선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 짱구녀석의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다. 짱구는 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.

총 조의 수 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

접근 방법

모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정!

일단 먼저 손으로 풀어 보았다.

N = 4, K = [4,3,2,1] 인 경우

[1,x,x,x] 일때 경우의 수 ⇒ 3!

[2,x, x, x] ⇒ 3!

[3, x, x, x] ⇒ 3!

⇒ 3 * 3! = 18

[4,1,x,x] 일때 경우의 수 ⇒ 2!

[4,2,xx] ⇒ 2!

⇒ 2 * 2! = 4

[4,3,1,2]일 때 경우의 수 ⇒ 1

⇒ 1

결과는 23

반복해서 팩토리얼을 구해야 하므로 팩토리얼 함수를 활용 해야 할 것.

1 .경우의 수를 계산할 함수 factorial을 선언한다.

 function factorial(n){
    if(n <= 1)return 1
    return n * factorial(n-1)
  }

2. 리턴값인 발표 순서를 할당할 변수 order 선언

isChecked 배열은 N=3일 때 [false,false,false,false]가 되고,

이어서 나올 코드에서 지나온 조를 true로 바꿔주어 지나오지 않은 조의 개수를 셀 때 false의 개수를 세는 방식을 사용하기 위해 선언해주었다.

(같은 조가 여러번 발표를 하지 않기 때문에 for문 바깥에 선언한다.)

0번째 인덱스는 계산을 편하게 하기 위한 더미데이터이다. (조는 1조부터 시작하기때문에)

let order = 0;

let isChecked = new Array(N+1).fill(false)

3. 반복문을 통해 각 인덱스마다 지나온 경우의 수를 계산하고 order에 더해준다.

예를 들자면

1. N=4, K=[4,3,2,1] 일 때, K[0]에서는 [1,x,x,x], [2,x,x,x], [3,x,x,x] 의 모든 경우의 수를 지나왔기 때문에, order에 (3x3!)를 할당해둔다.

3은 isChecked.slice(1,num)=[false,false,false, true]에서 false만 필터링한 [false,false,false].length = 3이다.
3!은 각 인덱스에서 구할 수 있는 모든 경우의 수이다.

2. K[1]에서는 [4,1,x,x], [4,2,x,x] 의 모든 경우의 수를 더해서 order에 누적시킨다. 2 *(2!)를 order에 더해준다.

3. K[2]에서는 [4,3,1,x]의 모든 경우의 수를 더해서 order에 누적시킨다. 1!를 order에 더해준다.

4. order = 18 + 4 + 1 = 23이다.

for (let i = 0; i < K.length; i++) {
    // K의 i번째 조를 변수에 담습니다.
    const num = K[i];
    // 사용했는지 판별하기 위해 isUsed에 체크합니다. (중복이 아니기 때문에)
    isUsed[num] = true;
    // num보다 앞에 올 수 있는 수들의 배열을 복제해서,
    const candidates = isUsed.slice(1, num);
    // 이 중에서 아직 사용되지 않은 수의 개수를 구합니다.
    const validCnt = candidates.filter((el) => el === false).length;
    // 아직 사용되지 않은 수, 그 전까지의 모든 경우의 수를 카운트합니다.
    const formerCnt = validCnt * factorial(N - i - 1);
    // order에 추가합니다.
    order = order + formerCnt;
  }