브루트 포스 - 멘토링

문제

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

입력 설명

M개의 줄에 걸쳐 수학테스트 결과가 학생번호로 주어진다. 학생번호가 제일 앞에서부터 1등, 2등, ...N등 순으로 표현된다.
만약 N=4이고, 테스트 결과가 3 4 1 2로 입력되었다면 3번 학생이 1등, 4번 학생이 2등, 1번 학생이 3등, 2번 학생이 4등을 의미한다.

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

데이터가 다음과 같은 형태로 주어진다.

출력 설명

짝을 만들 수 있는 총 경우의 수를 출력하시오.

 

입력 예제

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

 

출력 예제

3

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

 

---

 

내 풀이

• M번 수학 풀이를 진행했을 때의 등수를 각 학생마다 저장한다.
  • 위의 예시를 예로 들면, 1번 학생은 총 3번의 수학 풀이를 진행하면서 [3,4,2] 즉, 3등, 4등, 2등을 기록했다.
  • 1 ➡ [3,4,2] , 2 ➡ [4,3,4] , 3 ➡ [1,2,1] , 4 ➡ [2,1,3] 이렇게 저장할 수 있다.
• (멘토, 멘티)의 짝을 지어, 성립하는지 확인한다.
  • 1번이 멘토일때 멘티가 될 수 있는 사람들은 2,3,4이다.
  • 같은 방식으로 2번이 멘토일 때 멘티가 될 수 있는 사람들은 1,3,4이다.
  • 멘토와 멘티들의 등수를 비교해서 멘토의 모든 등수가 멘티보다 높다면 결과값을 +1 한다.

 

function solution(arr) {
  let result = 0;
  const table = {};

  for (let i = 0; i < arr.length; i += 1) {
    for (let j = 0; j < arr[i].length; j += 1) {
      if (table[arr[i][j]]) {
        table[arr[i][j]].push(j + 1);
      } else {
        table[arr[i][j]] = [];
        table[arr[i][j]].push(j + 1);
      }
    }
  }

  for (const key in table) {
    const mentor = key;
    const candidated = Object.keys(table).filter((student) => student !== key);
    candidated.forEach((student) => {
      if (table[student].every((ranking, i) => table[mentor][i] > ranking)) {
        result += 1;
      }
    });
  }

  return result;
}

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

 

 

첫번째 과정을 위해 객체를 활용하면 좋을 것 같다고 판단했다.

그리고 객체의 키값을 순회하며 (멘토, 멘티) 짝의 조건에 어울리는지 판단했다.

 

풀이 과정을 적는 것은 어렵지 않았으나, 코드를 작성하면서 객체를 활용하고 객체의 키값을 순회하는 과정이 조금 까다롭게 느껴졌다.

 

---

 

다른 방법은 반복문을 사용해 완전탐색을 진행하는 것이다.

 

예를 들어 학생이 4명이면 짝을 지을 수 있는 경우의 수는 4x4=16가지이다.

단, 이 경우에는 자기 자신과 짝을 짓는 경우도 포함하기 때문에 이때는 제외해야한다.

그리고 주어진 2차원 배열인 입력값을 활용해 M(풀이 횟수)번 순회하며 매 순회마다의 멘토가 되는 대상의 등수와 멘티가 되는 대상의 등수를 구해서 멘토가 될 수 있는 조건을 만족하는지 확인하면 된다.

 

말로 표현하는 것보다 코드를 보면 더 이해가 쉽다.

function solution(n, m, test) {
  let result = 0;
  const tmp = [];

  for (let i = 1; i <= n; i += 1) {
    for (let j = 1; j <= n; j += 1) {
      let cnt = 0;
      if (i === j) continue; // 자기 자신과 매칭되는 경우는 제외한다.

      for (let t = 0; t < m; t += 1) {
        let ir = -1;
        let jr = -1;
        for (let k = 0; k < n; k += 1) {
          if (arr[t][k] === i) ir = k; // 멘토의 등수를 구한다.
          if (arr[t][k] === j) jr = k; // 멘티의 등수를 구한다.
        }
        if (ir < jr) cnt += 1; // 멘토의 등수가 더 높으면 카운트한다.
      }

      if (cnt === m) { // m번 모두 멘토의 등수가 높다면 결과를 +1 한다.
        result += 1;
        tmp.push([i, j]);
      }
    }
  }

  console.log(tmp);
  return result;
}

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