[JS] 알고리즘 기초 정복 4-3번_멘토링

문제 4-3번

현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니 다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다. 선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정합니다. 만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 합니다. M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하세요.

 

🍄 입력설명

첫 번째 줄에 반 학생 수 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등을 의미합니다.

 

🍄 출력설명

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

 

🍄 입력예제 1

4 3

3 4 1 2

4 3 2 1

3 1 4 2

 

🍄 출력예제 1

3

(3, 1), (3, 2), (4, 2)와 같이 3가지 경우의 (멘토, 멘티) 짝을 만들 수 있다.

 

---

정답 코드

  - for문을 총 4번 돈다. 2번의 for문은 (i,j)를 선정해주는 것 1부터 n까지 (예제에서는 1부터 4까지) 총 16개의 케이스를 만들어준다 
    (0,1)(0,2) ... (4,4)
 - 테스트 횟수는 총 m번이고, m번 횟수만큼 for문을 도는데, 한 횟수 안에서 n명의 학생의 등수가 있으므로, 또 for문을 돌아준다.
   for문을 돌면서 i번째 학생의 등수를 구한다. j번째 학생의 등수를 구해서 비교하는데, i가 멘토가 되려면 등수가 무조건 j번보다 낮아야한다. 그리고 m번의 테스트마다 등수가 낮아야 하기 때문에, 한 테스트마다 등수가 낮다면 cnt를 ++ 해준다. cnt가 테스트 갯수만큼이 된다면 (i,j)는 멘토가 될 수 있다. 

function solution(arr) {
        let answer = 0;
        m = arr.length; //테스트 횟수 m은 3이 된다
        n = arr[0].length; // n은 학생수로 4가 된다.
        for (let i = 1; i <= n; i++) {
          // 1번부터 n번 학생까지
          for (let j = 0; j <= n; j++) {
            // 1번부터 n번 학생까지
            // 여기 까지 멘토 멘트를 정했다 (i, j)
            let cnt = 0; //테스트 시작하기 전에 cnt를 0으로 초기화한다.
            for (let k = 0; k < m; k++) {
              //테스트 3개 돌기
              let pi = pj = 0; //등수
              for (let s = 0; s < n; s++) {
                //테스트에서 등수 돌기
                if (arr[k][s] === i) pi = s; //k번째 테스트의 s번째 위치에 i번 학생이 있다면 pi 등수는 s다
                if (arr[k][s] === j) pj = s;
              }
              if (pi < pj) cnt++;
            }
            // cnt가 모든 테스트 m번에 위 조건이 성립하다면,
            if (cnt === m) answer++;
          }
        }
        return answer;
      }
      
let arr = [
	[3, 4, 1, 2],
    [4, 3, 2, 1],
    [3, 1, 4, 2],
    ];
console.log(solution(arr));
// 3 출력