[완전탐색] 멘토링

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

M번의 시험 결과 등수를 가지고 멘토와 멘티를 정한다.

만약 A학생이 멘토, B학생이 멘티가 되려면 A학생은 M번의 시험에서 모두 B학생보다 높은 등수를 얻어야 한다.

M번의 시험 결과가 주어졌을 때 멘토, 멘티의 짝을 만들 수 있는 경우가 총 몇 가지인지 출력한다.

 

 

👉 입력

학생 수(N)와 테스트 수(M)가 주어지고 M개의 테스트 결과가 학생번호로 주어진다.

제일 앞에서부터 1, 2, 3, ..., N등의 순서이다.

만약 N=4이고 3, 1, 4, 2의 입력이 주어졌다면 3번 학생이 1등, 1번 학생이 2등, 4번 학생이 3등, 2번 학생이 4등이다.

 

 

👈 출력

멘토와 멘티의 짝을 만들 수 있는 경우의 수를 출력한다.

 

 

📝 풀이

 

function solution(test) {
    let answer = 0;
    let arr = []
    let m = test.length;
    let n = test[0].length;

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            let count = 0;
            for (let k = 0; k < m; k++) {
                let pi = 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) count++;
            }
            if (count === m) answer++;
        }
    }
    return answer;
}

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

 

먼저 i와 j의 for문은 i를 멘토, j를 멘티라고 생각하고 가능한 학생의 조합을 나타낸다.

그리고 k와 s의 for문은 k가 행, j가 열으로 테스트 결과를 순회한다.

 

테스트 결과는 각 학생의 번호를 뜻하기 때문에 테스트 결과를 순회할 때 각각 i, j와 값이 동일한 것의 s 인덱스가 해당 학생의 등수가 된다.

따라서 i와 j의 등수를 각각 pi, pj에 저장한 후 pi가 pj보다 작으면(등수가 높으면) count값에 1을 더해가며 그 수를 센다.

 

k의 for문을 다 순회하면 테스트 결과의 순회가 끝난 것이다.

이때 count의 수가 테스트 횟수와 같으면 모든 테스트에서 i의 등수가 j의 등수보다 높았다는 뜻이므로 answer에 1을 더해준다.

 

모든 for문의 순회를 마치고 나면 모든 테스트 결과에서 i의 등수가 j의 등수보다 높은 경우의 수만 answer에 남게 되므로 answer를 리턴, 출력한다.