Algorithm

멘토링 짝 찾기 알고리즘

멘토링 짝 찾기 알고리즘

문제

현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다.

선생님은 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등을 의미합니다.

출력설명

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

예제

const students = 4; // 학생의 수
const tests = 3; // 테스트 횟수
const arr = [
  [3, 4, 1, 2],
  [4, 3, 2, 1],
  [3, 1, 4, 2],
]; // 등수
3

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

문제 이해하기

핵심 포인트

모든 학생 조합을 확인하되, 모든 테스트에서 멘토가 멘티보다 등수가 앞서는지 검증해야 합니다.

해결 전략

데이터 전처리

각 학생이 각 테스트에서 받은 등수를 저장하는 2차원 배열을 생성합니다.

const ranked = Array.from({ length: students }, () => []);

for (let test = 0; test < tests; test++) {
  for (let rank = 0; rank < students; rank++) {
    const student = arr[test][rank];
    ranked[student - 1][test] = rank;
  }
}

모든 학생 쌍 확인

모든 학생 조합 (멘토, 멘티)에 대해 검증합니다. 자기 자신은 제외합니다.

for (let mentor = 0; mentor < students; mentor++) {
  for (let mentee = 0; mentee < students; mentee++) {
    if (mentor === mentee) continue;
    // 검증 로직
  }
}

모든 테스트 검증

해당 학생 쌍이 모든 테스트에서 멘토 > 멘티 조건을 만족하는지 확인합니다.

let canBePair = true;

for (let test = 0; test < tests; test++) {
  if (ranked[mentor][test] >= ranked[mentee][test]) {
    canBePair = false;
    break; // 조기 종료
  }
}

if (canBePair) answer++;

나의 풀이

1단계: 등수 데이터 변환

한 배열 당 한 학생이 받은 등수를 담습니다.

const ranked = Array.from({ length: students }, () => []);

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < students; j++) {
    const student = arr[i][j];
    ranked[student - 1][i] = j;
  }
}

멘토링 등수 변환

2단계: 멘토-멘티 조합 확인

1번의 학생이 나머지 2-4번 학생과 등수를 비교했을 때, 모든 테스트에서 등수가 높다면 멘토-멘티 관계가 성립됩니다.

let answer = 0;

for (let mentor = 0; mentor < ranked.length; mentor++) {
  for (let mentee = 0; mentee < ranked.length; mentee++) {
    // 자기 자신은 제외
    if (mentor === mentee) continue;

    // 모든 테스트에서 멘토가 멘티보다 앞서는지 확인
    let canBePair = true;

    for (let test = 0; test < tests; test++) {
      if (ranked[mentor][test] >= ranked[mentee][test]) {
        canBePair = false;
        break;
      }
    }

    // 모든 테스트를 통과했다면 멘토 멘티 관계 성립
    if (canBePair) {
      answer++;
    }
  }
}

return answer;

Solution

solution.ts
function solution(students: number, tests: number, arr: number[][]): number {
  // 1. 전처리: 각 학생의 테스트별 등수 저장
  const ranked = Array.from({ length: students }, () => []);

  for (let test = 0; test < tests; test++) {
    for (let rank = 0; rank < students; rank++) {
      const studentId = arr[test][rank];
      ranked[studentId - 1][test] = rank;
    }
  }

  let answer = 0;

  // 2. 모든 쌍 확인 (조기 종료 최적화)
  for (let mentor = 0; mentor < students; mentor++) {
    for (let mentee = 0; mentee < students; mentee++) {
      if (mentor === mentee) continue;

      // 3. 모든 테스트 확인 (하나라도 실패하면 즉시 중단)
      let isValid = true;
      for (let test = 0; test < tests; test++) {
        if (ranked[mentor][test] >= ranked[mentee][test]) {
          isValid = false;
          break; // ✅ 조기 종료
        }
      }

      if (isValid) answer++;
    }
  }

  return answer;
}

시간 복잡도: O(N² × M) - N명의 학생에 대해 모든 쌍을 확인하고, 각 쌍마다 M개의 테스트를 검증합니다.

공간 복잡도: O(N × M) - 각 학생의 테스트별 등수를 저장하는 2차원 배열이 필요합니다.

Review

등수를 저장하는 것까지는 어렵지 않았으나, 그 값을 어떻게 비교해야할지 감이 안왔던 것 같습니다. 2중 for문을 넘어가는 순간 머리가 하얘진달까요..?

변수값을 mentor, mentee로 선언해서 작업하니 내가 어떤 값을 비교하고 있고 어떤 값을 찾고있는 건지 직관적으로 이해할 수 있었던 것 같습니다.

주의사항

브루트포스 알고리즘은 간단하지만, 데이터가 커지면 성능 문제가 발생할 수 있습니다. 이 문제는 N ≤ 20, M ≤ 10으로 제약이 있어 충분히 효율적입니다.