2022-02-02 / 사전식배열에서 특정 순서 찾기 orderOfPresentation

문제

 

input :조의 개수(N)와 조의 발표 순서(K)를 인자로 받는 함수 구현이다.
모든 경우의 발표 순서 중에 인자로 받은 발표 순서가 몇 번째(output)인지 확인해야 한다.

 

 

유의사항

 

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

ex) N = 3일 경우,[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

 

 

입출력 예시

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

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

 

접근 과정

 - N이 최대 12이므로 12개의 요소로 만들 수 있는 순열의 개수는 12!이다. 12! 은 내 통장 잔고보다 훨씬 크므로

 

12! 의 케이스를 모두 구현한 다음 거기서 몇 번째 배열인지 확인하려고 했지만 의미가 없었다.

 

 

- 그러면 고등학교 때 풀었던 순열과 조합을 생각해보자.

 

예를 들어 A, B, C, D, E를 사전식 배열로 나타내는데 arr = [C, E, A, C, B]는 몇 번째 순서로 튀어나오는가? 에 대해 생각해본다.

 

1. 우선 arr의 첫 번째 요소 C부터 살펴봐야 한다.  왜냐하면 사전식 배열은 AZZZZ 가 BAAAAA 가 앞에 있게 되는데 

 

이는 가장 앞에 있는 요소부터 차례로 순서를 판단하기 때문이다.

 

arr의 첫 번째 요소 C는 [A X X X X], [B X X X X]보다 더 나중 순서로 배열된다.  

 

따라서 뭐가 됐든간 순서는 [A X X X X]  [B X X X X]를 팩토리얼로 돌린 4!  + 4! 보다 뒷 순서이다.

 

(여기서 4! 은 각각 X 4개를 순열로 돌린 개수)

 

2. 그러면 이제 arr의 다음 요소인 E는 [C A X X X ]  [C B X X X] [C D X X X] 보다  나중 순서이다.

 

그러면 적어도 순서는 [C A X X X] [C B X X X] [C D X X X]를 팩토리얼로 돌린 3! + 3! + 3! = 3 x 3! 보다는 뒷 순서일 것이다.

 

 

3. 그러면 여기서 결과를 관찰해 우리에게 필요한 부분이 뭔지 본다.

 

 - 1. 의 결과가 4! + 4! 이 나온 이유를 분석하면 

•   4! 은  전체 배열의 길이 5에서 첫 번째요소가 들어갈 자리 1개를 뺀 5 - 1을 팩토리얼로 돌렸으며 
• 4! 을 2번 더한 이유는 첫번째 요소 C보다 앞의 사전식 순서가 A, B 두 개 이기 때문이다.

 

- 2. 의 결과가 3! + 3! + 3! 이 나온 이유를 분석하면

• 3! 은 전체 배열의 길이 5에서 첫 번째요소는 정해졌고 두번째요소가 들어갈 자리 1개를 더 뺀 5 - 2를 팩토리얼로 돌렸으며
• 3! 을 3번 더한 이유는 두번째 요소 E보다 앞의 사전식 순서가 A, B, C, D 4개이긴 하지만 이미 C를 첫번째 요소로 썼으니 3개이기 때문이다.

 

전략 수립

 

- 종합하면 필요한 부분은 

• 주어진 배열의 첫 번째 요소부터 반복하며 `(배열의 길이) - (이미 배열 안에 배치된 요소의 길이) ` 를 팩토리얼로 돌리는 부분!

• 반복문을 사용해 배열을 돌린다. -- (가)
• 이미 배열안에 요소(숫자)가 배치되었는지 아닌지의 여부 판단해야 함. --- (나)

• 배열 반복 중 해당 요소보다 아직 미사용이면서 앞의 순서들의 개수를 세어 팩토리얼을 그 개수만큼 더하는 부분! --- (다)
• 그것들을 계속하여 순서로  합산하는 부분! --- (라)

4가지가 필요하지 않나 생각한다.

 

코드 작성

function orderOfPresentation (N, K) {
    // TODO: 여기에 코드를 작성합니다.
  // count 변수 저장
  let order = 0;


  // 우선 팩토리얼 함수 만듬
  const factorial = function (num) {
    // 메모리 최적화 해줘야됨 아직 안해줌
    // base case
    if (num <= 1) { return num }
    // recurtion
    return num * factorial(num - 1)
  }

  // 숫자가 이미 사용되었는지 아닌지 여부를 boolean으로 판단함. N + 1 인이유는 0번쨰 인덱스는 더미
  let usedNumber = new Array(N + 1).fill(false) // (나)

  // 배열 K를 K의 길이만큼순회하면서
  // 배열 K의 i번째인덱스의 요소(숫자)보다 작은 것들을
  // 팩토리얼로 돌린다.
  for (let i = 0; i < K.length; i++) { // (가)
    //사용한 숫자를 체크하기위해 요소가 들어오면 usedNumber부분을 true로 바꿔줌 // 
    usedNumber[ K[i] ] = true; // (나)
    //K의 i번째 요소의 값 미만이고 아직 사용하지 않은 숫자들을 카운트해야 함
    let lessNumbers = usedNumber.slice(1, K[i]).filter( el => el === false).length // (다)
    // 팩토리얼로 count를 돌림
    let count = lessNumbers * factorial(N - i - 1) // (다)
    // order에다가 누적으로 저장
    order += count; // (라)
  }

  return order

}
debugger;
console.log(orderOfPresentation(3, [2, 3, 1]))

 

느낀 점

 

사실 이 문제를 처음 보고 못 풀었다.

 

그리고 레퍼런스 코드를 봐도 이해하지 못했다. 왜 무슨 숫자를 저장해야 하고 뭘 해야 하지 그냥 순열인데?

 

그런데 계속 생각날 때마다 코드를 분석해보니 왜 사용한 숫자를 저장해야 하는지 등의 이유들을 깨닫게 되었다.

 

그리고 어떠한 어려운 문제에 부딪쳤을 때 분석해서 순서대로 코드를 따른 연습에 도움이 되었고

 

또한 조금 더 전문적으로 문제를 분석하고 이해할 수  있게 되었다.

 

발전할 점

 

조금 더 설명이 장황한 느낌인데 그것을 깔끔히 그리고 핵심을 파악하기 위해 노력해야겠다