알고리즘 1 : 발표순서

발표순서

선생님은 짱구에게 발표할 조의 수 N과 발표 순서 k를 말해준다. 짱구는 모든 경우의 수를 따지고 k 순서가 몇 번째 경우의 수인지 대답해야 한다. 짱구가 올바른 답을 말할 수 있게 알고리즘을 작성해보자.

 

인자 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

 

 

---

코드

function orderOfPresentation (N, K) {
    
  function factorial(n){//팩토리얼은 모든 경우의 수 이다.
    if(n===0)return 1
    return n*factorial(n-1)
  }
  
  let order = 0; // order은 K배열에 오기까지 지나온 배열(발표순서)들의 개수를 할당할 변수이다.
  //예를 들면 N=3,K=[2,3,1]일 때, [2,3,1]앞에 [1,2,3],[1,3,2],[2,1,3] 총 3개의 순서가 있다.
  
  let isChecked = new Array(N+1).fill(false)//
  //isChecked는 K의 각 인덱스마다 지나온 조를 체크해 놓을 배열이다.
  //예를들면 K=[2,3,1]일 때, K[0]에서는 1조가 제일 먼저 발표하는 모든 경우의 수를 지나왔기 때문에 
  //isChecked[1]에 true를 할당할 것이다.
  //N=3이라면 [false,false,false,false]인데 인덱스는 0부터 시작하지만 조는 1부터 시작하기 때문에 
  //계산의 편의를 위해 0번째 인덱스에 더미데이터를 추가하였다.
  
  //K의 길이만큼 순회한다.
  for(let i = 0;i<K.length;i++){
    const num=K[i]//K의 i번째 조를 변수에 담는디.
    isChecked[num]=true//이미 발표했는지 판별하기 위해 사용한다. 
    let passedNum = isChecked.slice(1,num).filter(i=> i===false).length//아직 발표하지 않은 조의 개수를 구한다.
    order += passedNum * factorial(N-1-i)//경우의 수를 카운트하여 order에 추가한다.
  }
  
return order
}

상세 설명

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

 function factorial(n){
    if(n===0)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에 더해준다.

order는 아래 그림과 같이 각 인덱스에서 구한 경우의 수가 다 누적된다.

예를 들자면

 

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

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

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

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

4. order = 12 + 2 + 1 = 15이다.

  for(let i = 0;i<K.length;i++){
    num=K[i]//2
    isChecked[num]=true//[f,f,t,f]
    
    let passedNum = isChecked.slice(1,num).filter(i=> i===false).length//
    //slice를 이용해 0번째 인덱스를 계산에서 제외한다.
    //filter를 이용해 false의 개수를 센다. false는 아직 지나오지 않은 조이다.
    
    
    order += passedNum * factorial(N-1-i)
  }