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	인자1 : K
Number 타입의 1 <= N <= 12인 조의 개수	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이 됩니다.

 

출력:

• number 타입을 리턴해야 합니다.

 

주의사항:

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

입출력 예시:

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

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

 

 

📝 이 문제는... 

경우의 수의 성격을 캐치할 수 있어야 효율적으로 풀 수 있다.

 

---

💡 잠깐! 아이디어 생각해보기

 

만약, 아래의 코드가 들어왔다면 

 

orderOfPresentation(3, [2, 3, 1]);

 

일단 1,2,3 세개의 숫자로 만들 수 있는 모든 경우의 수는 아래와 같을 것이다.

 

 

그럼 이 중에 [2, 3, 1]은 어떤 규칙으로 안에 들어있을까?

아래의 그림을 참고하자.

 

보다시피 이전 가지에서 나올 수 있는 모든 숫자들을 더하면 구하고자하는 값이 몇번째로 등장하는지 알 수 있다.

더 긴 배열의 경우를 보려면 아래 더보기 클릭한다.

 

----------------

----------------

 

 

그럼 이전 가지에서 몇가지의 경우의 수가 나왔는지 알기 위해서 모든 경우의 수를 구해야할까?

다행히도 그럴 필요가 없다.

 

 

이쯤되면 어느정도 규칙성이 보인다.

 

 

그럼 이제 팩토리얼 앞에 붙어있는 이전 경우의 수에 해당하는 숫자는 어떻게 구해주면 좋을까?

이때 이전 순서에 어떤 경우에 수가 있을지 파악하기 위해

base라는 N개의 원소를 오름차순으로 갖고 있는 가장 기본 배열을 하나 만들어준다.

 

 

이제 여기까지 했으면 그림보다 코드를 보는게 더 이해가 빠를 수도 있다.

 

 

---

 

🌟 문제풀이

 

function orderOfPresentation (N, K) {
  //N개의 원소가 오름차순으로 담긴 base배열을 순서 파악용으로 만듬
  let base = [];
  for(let i=1; i<=N; i++){
    base.push(i)
  } 

  let result = 0;

  while(K.length > 0){
    //base인덱스에서 K[0] 앞에 몇개의 원소가 있나?
    //이전 가짓수 묶음의 수을 구하는 작업
    let numOfCasesGroups = base.indexOf(K[0]);
    
    //묶음 안에 가짓수의 수를 구하는 작업
    let numOfCases = 1; 
    for(let i=K.length-1; i>=1; i--){
        numOfCases *= i
    }
    
    result += (numOfCasesGroups * numOfCases)
    K.shift() //이제 경우의 수에서 고려할 필요없는 원소는 제외 시키기
    base.splice(numOfCasesGroups,1) //이제 순서에서 고려할 필요없는 원소는 제외 시키기
  }
  return result 
}

 

뭔가 감으로 풀었는데

풀고나서 해설을 하려니 영 어렵다.

 

결국 요약하자면,

큰 가지부터 이전 가지들의 숫자를 더해가면서 파악하고자 하는 배열의 가짓수에 도달하는 방법이다.

 

좀 더 매끄럽게 설명할 수 있는 방법이 있다면 추가하도록 하겠다.