[Algorithms] 멘토멘티

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

전형적인 블루투포스(완전탐색) 문제이죠.

코드 먼저 짜보고 설명해볼게요.

 

function solution(test) {
	let answer = 0;
	let testCount = test.length;         // 테스트 횟수 (행의 개수)
	let studentCount = test[0].length;  // 학생 수 (열의 개수)

	for (let i = 1; i <= studentCount; i++) {          // 학생 i
		for (let j = 1; j <= studentCount; j++) {      // 학생 j
			if (i === j) continue;  // 자기 자신과 비교할 필요는 없음
			let cnt = 0;           // i가 j보다 앞선 횟수

			for (let k = 0; k < testCount; k++) {      // 테스트마다
				let pi = 0, pj = 0;  // 현재 테스트에서 i와 j의 순서

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

				if (pi < pj) cnt++;  // i가 j보다 앞서 있으면 카운트
			}

			if (cnt === testCount) answer++;  // 모든 테스트에서 i가 j보다 앞섰다면 정답++
		}
	}

	return answer;
}

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

 

• 모든 테스트에서 i가 항상 j보다 앞선다면 그 쌍을 멘토-멘티로 인정합니다.

i와 j는 각각 학생 번호입니다.
자기 자신끼리 비교하지 않으니 if(i === j) continue;를 넣었습니다.

현재 테스트(k)에서 i와 j가 각각 몇 번째에 있는지 찾습니다.
test[k]는 한 번의 테스트 결과이고, s를 돌면서 i와 j의 순서를 기록합니다.
→ pi가 pj보다 작다면, i가 더 앞섰다는 뜻입니다.

 

cnt가 테스트 횟수와 같다면, 모든 테스트에서 i가 j를 이겼다는 뜻이므로 answer를 1 증가시킵니다.