[알고리즘]멘토링 - 완전탐색

문제

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

 

입력예제

4 3 //학생수 N, 테스트 횟수 M
3 4 1 2
4 3 2 1
3 1 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;
              let 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 (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) { //멘토 i 일 때, 멘토 j 가 되는 모든 경우의 수
    let cnt = 0;
    for (let k = 0; k < m; k++) { //m만큼의 테스트 k에서 학생의 수 만큼 s를 돌며 위치(등수)를 얻음
      let pi = 0; //학생 i의 자릿값 초기화
      let pj = 0; //학생 j의 자릿값 초기화
      for (let s = 0; s < n; s++) {
        if (test[k][s] === i) pi = s; //k번째 test에서 s의 값이 i와 같다면, pi는 s 즉 i의 위치를 얻음(몇등인지!)
        if (test[k][s] === j) pj = s; //k번째 test에서 s의 값이 j와 같다면, pj는 j의 위치값을 할당받음 
      }
      if (pi < pj) cnt++; //얻은 결과값을 비교해 i가 멘토가 되는 조건에 부합된다면 cnt를 카운트
    }
    if (cnt === m) answer++; 
  } //모든 k 만큼의 test를 다 돌고 cnt가 m, 테스트 횟수와 같다면 조건에 부합하므로 answer에 카운트
}