Mentoring

Problem

Hyunsoo’s class teacher wants to create a mentoring system to improve the students’ math scores. Mentoring is a pair of mentors (students helping) and mentees (students receiving help), and the mentor helps the mentee study math.
The teacher selects a mentor and a mentee based on the M number of math test scores.
If student A is a mentor and student B becomes a mentee, student A must have a higher rank than student B in the M math test.
Write a program that prints out the total number of cases in which a mentor and mentee pair can be made when M math scores are given.

input

• The first line gives the number of students in the class N(1<=N<=20) and M(1<=M<=10).
• From the second line to M lines, the math test results are given as student numbers. Student numbers are expressed in the order of 1st, 2nd, …N, etc. from the front.
• If N=4 per line and the test result is entered as 3 4 1 2, it means that student 3 is 1st, student 4 is 2nd, student 1 is 3rd, and student 2 is 4th.

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

output

The first line prints the total number of possible pairs.

3

(3, 1), (3, 2), (4, 2) There are 3 cases of (mentor, mentee) pair can be made.

Solution

O(n^2) Calculate minimum available mentor-menty set

function solution(test) {
	let answer = 0;

	const set = {
		1: [],
		2: [],
		3: [],
		4: [],
	};

	// calculate available metor-menti set for each montor
	// result[0] can be a mentor for remains, so available menties gonna be 3.
	// it can be calculted by all student[result.length] - 1 - current student index
	for (let result of test) {
		for (let j in result) {
			set[result[j]].push(parseInt(result.length - 1 - j));
		}
	}

	// add minimum number for mentor-menti set each other
	for (let x of Object.values(set)) {
		answer += Math.min(...x);
	}

	return answer;
}

O(n^4)

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

	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 = (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) {
				tmp.push([i, j]);
				answer++;
			}
		}
	}
	console.log(tmp);

	return answer;
}