[완전탐색(블루투포스)] - 멘토링

2022.01.29 - [자료] - JS알고리즘 참고자료 및 시작세팅

---

문제

 

밑의 각줄은 시험회차 마다의 학생번호가 나열 되어있다.

3 4 1 2

4 3 2 1

3 1 4 2

 

3 4 1 2면 3번 학생이 1등 4번학생이 2등 이라는 뜻이다. 시험은 3줄이라 3번 치뤘다고 보면된다.

여기서 A학생이 B 학생보다 3번의 시험에서 모두 등수가 높아야만 멘토와 멘티가 될 수 있다.

몇 가지의 짝이 이루어질까?

 

 

풀이

우선 모든 학생들의 반복문을 돌려준다.

1번 학생이 멘토이고 1~4번 학생이 멘티일때,

2번 학생이 멘토이고 1~4번 학생이 멘티일때

3번 학생이 멘토이고 1~4번 학생이 멘티일때

4번 학생이 멘토일때 1~4번 학생이 멘티일때

총 4 x 4 = 16번의 상황을 전부 봐야한다. 이걸 완전탐색(Brute Force)이라고 한다.

 

학생을 모두 확인하는 2중 for문에서 시험횟수 + 등수 만큼 또 반복을 해준다.

예를 들어서 멘토가 3번학생, 멘티가 1번 학생일때,

test	등수: 0등	1등	2등	3등
횟수 0번	3 번 학생	4	1번 학생	2
1번	4	3	2	1
2번	3	1	4	2

배열[횟수=0][등수=0] === 멘토학생(3) 이면 0등을 새 변수 rankI에 할당한다.

배열[횟수=0][등수=2] === 멘티학생(1) 이면 2등을 새 변수 rankJ에 할당한다.

 

등수 반복문을 4번 다돌고나서 rankI < rankJ 이면 count변수를 1 증가 시켜준다.

 

횟수 반복문을 다돌았을때 count === 테스트횟수 이면 answer변수를 1증가 시켜준다. 

 

코드

function solution(test){
  let answer=0;
  let studentNum = test[0].length;
  let testNum = test.length;
  //모든 학생을 반복문 돌아줌(부르트포스)
  for (let i = 1; i <= studentNum; i++) { //i가 멘토
    for (let j = 1; j <= studentNum; j++) { //j가 멘티
      //멘토인 i가 멘티인 j보다 등수가 높은지 확인해야함
      let count = 0;
      for (let k = 0; k < testNum; k++) { //시험 횟수만큼 반복
        let rankI = 0;
        let rankJ = 0;
        for (let l = 0; l < studentNum; l++) { //등수만큼 반복
          if (test[k][l] === i) rankI = l;
          if (test[k][l] === j) rankJ = l;
        }
        if (rankI < rankJ) count++;
      }
      if (count === testNum) answer++;
    }
  }

  return answer;
}

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

 

 

출처

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의