[알고리즘] 멘토링 - 완전 탐색, 브루트 포스 (JavaScript)

구미·2021년 8월 20일

알고리즘

목록 보기

18/25

✏️ 문제 설명

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

✏️ 입출력 예제

입력

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

출력

학생 순서쌍을 구하고 배열 내에서 특정 학생의 인덱스를 구하는 방법은 비교적 쉽게 떠올린 것 같아서 시간이 오래 걸리더라도 문제를 풀 수 있을 것 같았다.
그런데 순서쌍 배열을 만들고나서부터 각 순서쌍을 가지고 테스트 결과를 검증하는 데서 뇌절(...)이 왔다.

처음 떠올린 방식

const pairs = [];

for (let i = 1; i < n + 1; i++) {
  for (let j = i + 1; j < n + 1; j++ {
    pairs.push([i, j]);
  }
}

이렇게 하면 pairs 배열에는 [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] 의 값이 담긴다. 두 학생을 선택했을 때 멘토 - 멘티 관계가 되는 경우는 하나뿐이므로 (ex. 1이 멘토, 2가 멘티인 경우 2가 멘토, 1이 멘티가 될 수 없음) 이런 식의 순서쌍을 생각했는데 이게 오히려 문제 푸는 데 걸림돌이 됐다. 각 순서쌍마다 멘토 - 멘티 관계가 바뀌었을 때의 경우도 생각해야했기 때문에...

i, j 모두 1부터 n까지 for문을 도는 것으로 순서쌍을 만들고 나니 금방 해결할 수 있었다! 🥲

🔍 제출한 풀이

// 배열 안에서 특정 학생의 인덱스를 찾는 함수를 정의해줌
function findMyIndex(student, arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === student) {
      return i;
    }
  }
}

function solution(test) {
  const m = test.length;
  const n = test[0].length;
  
  let count = 0;
  const pairs = [];

  // 가능한 순서쌍을 pairs 배열에 모두 담아줌
  // [1, 1], [1, 2], ..., [4, 3], [4, 4]
  
  for (let i = 1; i < n + 1; i++) {
    for (let j = 1; j < n + 1; j++) {
      pairs.push([i, j]);
    }
  }

  // pairs 배열을 돌며 멘토 - 멘티가 가능한 경우만 count
  for ([a, b] of pairs) {
    let isPossible = true;

    for (array of test) {
      if (findMyIndex(a, array) >= findMyIndex(b, array)) {
        isPossible = false;
        break;
      }
    }

    // 모든 test에 대한 검증이 끝난 이후에도 isPossible === true 라면 count
    if (isPossible) count++;
  }
  return count;
}

배열을 돌며 멘토 - 멘티 관계를 검증할 때 arr.forEach()를 사용했다가 이렇게 할 경우 break를 쓸 수 없길래 위와 같은 방식으로 바꿨다.

arr.forEach((test) => {
// 멘토의 등수가 멘티의 등수와 같거나 낮은 경우 isPossible을 false로 바꾸고 반복문 탈출
// 멘토의 점수가 멘티의 점수보다 한 번이라도 낮은 경우 더 검증할 필요가 없기 때문
  if (findMyIndex(a, test) >= findMyIndex(b, test)) {
    isPossible = false;
    break;
  }
})

위처럼 쓸 경우 Uncaught SyntaxError: Illegal break statement 에러가 발생한다. 다음부터는 주의해서 사용해야겠음 😮

🔍 2차원 배열 인덱스를 이용한 풀이

풀이 예시

function solution(test) {
  let answer = 0;
  const m = test.length;
  const n = test[0].length;
  
  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) answer++;
    }
  }
  return answer;
}

강의에서 예시로 나왔던 풀이인데 for문을 4중으로 도는 게 좀 마음에 걸린다. 순서쌍 구하기 2중 for문, 순서쌍 검증하기 3중 for문 이렇게 나누면 좀 더 나은 것인지 아니면 m, n 범위가 크지 않아서 큰 상관 없는 건지 궁금 🤔

여튼 2차원 배열 인덱스 다루는 연습도 할 겸 이 방식대로 다시 풀어봤다.

내 풀이

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

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      pairs.push([i, j]);
    }
  }

  for ([a, b] of pairs) {
    let count = 0;
    for (let k = 0; k < m; k++) {
      // 각 테스트마다 a, b 학생의 인덱스를 기록하기 위한 변수 선언
      let pa = pb = 0;
      for (let s = 0; s < n; s++) {
        if (test[k][s] === a) pa = s;
        if (test[k][s] === b) pb = s;
      }
      // 각 테스트에 대한 검증이 완료된 경우 체크
      if (pa < pb) count++;
    }
    // 모든 테스트에 대한 검증을 끝냈을 때 테스트 횟수만큼 검증을 통과했다면 멘토 - 멘티 관계 성립
    if (count === m) answer++;
  }

  return answer;
}