완전탐색(Brute Force) 멘토링

현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니 다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다.
선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정합니다.

만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 합니다.
M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하세요.

 

1) 입력

첫 번째 줄에 반 학생 수 N(1<=N<=20)과 M(1<=M<=10)이 주어진다.
두 번째 줄부터 M개의 줄에 걸쳐 수학테스트 결과가 학생번호로 주어진다. 학생번호가 제일 앞에서부터 1등, 2등, ...N등 순으로 표현된다.
만약 한 줄에 N=4이고, 테스트 결과가 3 4 1 2로 입력되었다면 3번 학생이 1등, 4번 학생이 2등, 1번 학생이 3등, 2번 학생이 4등을 의미합니다.

 

 

2) 출력

첫 번째 줄에 짝을 만들 수 있는 총 경우를 출력합니다.

 

 

 

ex) 입력예제 

3 4 1 2
4 3 2 1
3 1 4 2

 

ex) 출력예제

3

(3, 1), (3, 2), (4, 2)

 

 

 

 

풀이)

function solution(test) {
  let answer = 0;

  let m = test.length;

  let n = test[0].length;

  

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
     let cnt = 0;
      for (let k = 0; k < m; k++) {
        let pi = 0,
          pj = 0;

        for (let s = 0; s < n; s++) {
          if (test[k][s] === i) pi = s;
          if (test[k][s] === j) pj = s;
         
        }
        if (pi < pj) cnt++;
      }
      if (cnt === m) answer++;
    }
  }

  return answer;
}

let arr = [
  [3, 4, 1, 2],
  [4, 3, 2, 1],
  [3, 1, 4, 2],
];
console.log(solution(arr));

짝을 만들수 있는 학생번호의 경우의수를 모두 구함 ( for 문)  => ex) (1 ,1),(1 ,2),(1 ,3),(1 ,4),(2, 1),(2,2)..... 

cnt 는 멘토와 멘티가 될수있는 경우의수가 모든 테스트에 예외가 없는지 비교해줄 카운팅수 => ex) 총 테스트가 3개면 cnt는 3이어야 됨

변수 pi = 멘토 ,pj = 멘티 는 해당 수학테스트별 학생번호의 index

멘토(i) 의 위치를 찾았을대 해당 index를 pi에 저장함

멘티(j) 의 위치를 찾았을대 해당 index를 pj에 저장함

 

pi의 index가 pj 의 index보다 작으면 cnt를 카운팅 해줌 (인덱스가 클수록 등수가 낮으니 반대가 되어야함)

 

하나의 테스트(변수 K) 의 for문이 끝나면 cnt 와 m(수학테스트 횟수) 가 동일하면 해당 멘토(i)가 멘티(j) 보다 수학 테스트의 모든결과가 앞서기 때문에 answer를 증감해준다.