[Inflearn] 자바 알고리즘 문제풀이 #02-12 12. 멘토링

문제

설명

현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니다.

멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다.

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

 

출력 

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

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

 

 

 

내 풀이

왜 답이 3인지 이해가 가지 않았다.

 

A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 한다는 조건이 있고

멘토가 3, 멘티가 1일 경우 멘토는 3번째 테스트에서 멘티보다 성적이 좋지 않고

멘토가 3, 멘티가 2일 경우멘토는 3번째 테스트에서 멘티보다 성적이 좋지 않은 것이 아닌가??

그래서 혼자 풀 때는 (4, 2) (멘토, 멘티)인 경우만 도출하게 풀었는데.....

그래서 2-11. 임시반장 정하기랑 풀이가 똑같음..

 

문제에 오류가 있다면 선생님이 수정하셨지 않을까?라는 의문점을 갖고 강의 커뮤니티에 찾아보니 내 해석에 오류가 있었다.

나는 행과 열을 이렇게 생각했기 때문에 (4, 2) (멘토, 멘티)인 경우만 가능하다고 생각했던 것.

0행 3 4 1 2로 설명을 하자면, 학생1 3등, 학생2 4등, 학생3 1등, 학생4 2등으로 해석한 것이다.

그래서 학생 1과 학생 2를 정한 후, 각 테스트 별 등수만 비교해서 3일 경우 답+1 해주는 코드로 풀었다.

 

 

 

그러나 내가 돌머리라 문제 이해를 잘 못 한거였다.

왜 알고리즘은 문제 이해하는 것도 어렵냐;; 문제 이해하는 게 문제임,,

똑같이 0행 3 4 1 2로 설명을 하자면, 학생3 1등, 학생4 2등, 학생1 3등, 학생2 4등으로 해석해야 하는 것이다.

 

 

 

그래도 혼자 푼 게 아까우니까 일단 내가 푼 코드 올림

import java.util.Scanner;

public class Main2_12 {
    public int Solution(int m, int n, int[][] arr) {
        int cnt, answer=0;
        for (int i = 0; i < n; i++) {
            cnt=0;
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if(arr[k][i] > arr[k][j]) // 숫자가 작은 것이 등수가 높은 것
                        cnt++;
                }
                if(cnt==3) answer++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main2_12 T = new Main2_12();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(T.Solution(m, n, arr));
    }
}

결과

 

 

 

선생님 풀이

import java.util.Scanner;

public class Main2_12 {
    public int Solution(int n, int m, int[][] arr) { // n : 학생 수, m : 테스트 수
        int answer=0;
        for (int i = 1; i <= n; i++) { // i : 멘토, j : 멘티
            for (int j = 1; j <= n; j++) { // 상위 두개 for문은 등수를 비교할 학생을 지정
                int cnt=0;
                for (int k = 0; k < m; k++) { // 각 테스트마다 (멘토, 멘티)의 등수를 구해 비교
                    int pi=0, pj=0; // pi : 멘토의 등수, pj : 멘티의 등수
                    for (int s = 0; s < n; s++) {
                        if(arr[k][s] == i) pi=s; // 배열 안의 값 : 학생 번호, 배열의 열 인덱스 번호 : 학생 등수
                        if(arr[k][s] == j) pj=s;
                    }
                    if(pi<pj) cnt++;
                }
                if(cnt==m) answer++; // cnt가 테스트 수와 같다면 모든 테스트에서 멘토의 점수가 높은 것
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main2_12 T = new Main2_12();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 학생 수
        int m = sc.nextInt(); // 테스트 수
        int[][] arr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(T.Solution(n, m, arr));
    }
}

결과

 

 

 

알게된 점

11. 임시반장 정하기 문제에서는 학생 2명(i, j)을 정해 각 열마다 i가 가진 배열의 값이랑 j가 가진 배열의 값을 비교해서(총 n번 비교) 같은 경우에만 정답+1을 했다.

 

12. 멘토링 문제에서는 학생 2명(i, j)을 정해 각 행(테스트)마다 i가 가진 배열의 열 인덱스 값이랑 j가 가진 배열의 열 인덱스 값을 비교해서(총 n*n번 비교) 모든 테스트에서 멘토가 점수가 높을 경우에만 정답+1을 했다.

 

 

11번 문제에서는 학생과 학년 정보가 순차적으로 되어 있어서 그 값을 그냥 사용해서 배열 값만 비교하면 됐었지만,

12번 문제에서는 먼저 입력으로 들어오는 (멘토, 멘티) 학생의 번호를 배열을 일일이 돌며 멘토와 멘티의 위치를 먼저 찾은 후에, 열 인덱스 값을 비교하는 것이기 때문에 반복 횟수의 차이가 생긴다. ==> 이것이 3중 for문으로 문제를 해결하냐, 4중 for문이 하냐의 차이같다.