발단
인프런 자바스크립트 알고리즘 문제풀이(코딩테스트 대비) 에서 제시된 완전 탐색 문제를 선생님의 풀이보다 for문 뎁스를 하나 더 줄여서 문제를 풀었는데 자랑할 데가 없어서 블로그를 작성하게 되었다.
문제 풀이에 앞서 이 알고리즘 문제와 모범 답안의 저작권은 앞서 언급한 인프런 자바스크립트 알고리즘 문제풀이(코딩테스트 대비) 강의의 저자인 김태원 선생님께 있습니다.
혹시라도 선생님께서 이 블로그 게시글을 발견하신다면 선생님의 알고리즘 문제와 모범 답안을 업로드 함에 부디 노여워마시고 댓글이나 메일 등 따로 연락 주시면 바로 내리도록 하겠습니다.
또한 제가 지금 이 강의를 2회차 복습하고 있는 열정적인 학생이며 이 강의는 선생님이 설명을 자세히 해주시고 또 문제 난이도도 적절하여 알고리즘 초심자가 듣기에 완벽한 강의라고 생각한다는 점 고려해주시길 바랍니다.
문제
현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니 다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다.
선생님은 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
3412
4321
3142▣ 출력예제
3답안
강의 해설
function solution(test){
let answer=0;
m=test.length; // 테스트 수
n=test[0].length; // 학생 수
// 학생 A
for(let i=1; i<=n; i++){
// 학생 B
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;
}
let arr=[[3, 4, 1, 2], [4, 3, 2, 1], [3, 1, 4, 2]];
console.log(solution(arr));이렇게 풀이할 경우 멘토 역과 멘티 역을 구분하여 찾기 때문에 학생 수 * 학생 수로 전체 16가지의 가짓 수를 중 멘토와 멘티를 만들 수 있는 경우의 수를 계산한다.
내 풀이
function getPossibleMentorMentiCount(studentCount, testCount, arr) {
// 가능한 짝의 수
let answer = 0
// 중복되지 않는 학생 수의 조합
for(let studentNum = 1; studentNum <= studentCount; studentNum++ ) {
for(let partnerNum = studentNum + 1; partnerNum <= studentCount; partnerNum++) {
// 파트너가 멘토가 될 수 있는 경우의 수
let possibleMentorCount = 0
// 파트너가 멘티가 될 수 있는 경우의 수
let possibleMentiCount = 0
// 중복 제외
if(studentNum !== partnerNum) {
// 테스트 마다 돌면서
for(let testNum = 0; testNum < testCount; testNum++ ) {
// 학생의 등수 찾기
let studentGrade = arr[testNum].indexOf(studentNum)
// 파트너의 등수 찾기
let partnerGrade = arr[testNum].indexOf(partnerNum)
// 파트너가 학생보다 시험을 잘 봐서 더 높은 등수를 받았다면
if(studentGrade > partnerGrade) ++possibleMentorCount
// 그게 아니라면
else ++possibleMentiCount
}
}
// 시험 횟수와 멘토 혹은 멘티가 될 수 있는 수가 같다면 짝으로 만들어준다
if(possibleMentiCount === testCount || possibleMentorCount === testCount) ++answer
}
}
return answer
}
console.log(getPossibleMentorMentiCount(4, 3, [
[3, 4, 1, 2],
[4, 3, 2, 1],
[3, 1, 4, 2]
]))멘토가 될 경우의 수와 멘티가 될 경우의 수를 구분하지 않고 두 학생이 짝이 될 수 있는 경우만 계산해 문제를 풀었다. 그 결과 선생님의 풀이에서 for문을 하나 줄일 수 있었다.
마무리
처음엔 사실 학생 별 * 테스트 별로 다른 학생의 멘토가 될 수 있는지 여부를 계산해서 풀었더니 총 4n의 4제곱의 시간복잡도가 발생했다.
선생님 해설을 참조해서 여러 번 풀어보는 게 다양한 관점에서 생각할 수 있어 좋은 것 같다.
혹시 이 풀이에서 오류를 발견하셨거나 오류가 발생할 수 있는 다른 입력 예제를 아시는 분은 댓글 달아주시면 감사하겠습니다.
참고문헌
