<2.12> 멘토링

문제
: 첫 번째 줄에 입력으로 "반 학생수" N 값과 수학테스트 횟수 M이 주어진다.
이후 M줄에 걸쳐 N명의 각 학생에 대하여 - 각 수학테스트에서의 등수가 주어진다. 이때 (멘토, 멘티) 관계로 이어질 수 있는 case 개수를 구하라.

a학생과 b학생이 (멘토, 멘티) 로 이어지기 위해서는 M번에 걸친 모든 수학테스트에서 a학생 등수가 b학생 등수보다 낮아야 한다.
(등수가 낮을수록 시험을 잘본것)
(1<=N<=20 , 1<=M<=10)

이 문제의 요구사항은 결국 주어진 입력에 따라 (멘토, 멘티)를 맺을 수 있는 경우의 수를 구하는 것이다.

1. 이때 나는 모호한 부분이 있었는데,
   예를 들어 a,b,c,d의 학생이 있었을 때 (a,b)학생이 멘토 멘티 관계가 맺어지면 (c,d)학생도 반드시 멘토 멘티 관계가 맺어저야 하는가? 였다.

• 이 부분은 문제의 예로 주어진 입력값을 가지고 시뮬레이션을 해본 결과 ,
  (3번 학생, 2번학생) 순서로 멘토 멘티 관계가 맺어지면 1번학생과 4번학생은 멘토-멘티 관계가 맺어질 수 없다는 것을 확인하였다.
• 따라서 주어진 학생들이 모두 멘토 멘티 관계를 맺어야 하는것은 아니고 ,
  단순히 멘토-멘티 관계를 맺을 수 있는 경우의 수만 파악하면 된다고 생각했다.

2. 또한 (a,b) 학생이 멘토 멘티관계가 맺어지면 , 경우의 수를 count할 때 (a,c) 학생이 멘토 멘티 관계가 맺어져도 , 이미 a학생은 b학생과 관계가 맺어졌으니, 이 (a,c)에 대한 경우의 수를 count하면 안되는 것인가? 였다.
   (즉 동시에 멘토 멘티 관계를 맺을 수 있는 경우를 포함하는지의 여부)

• 다행이 이 부분은 문제의 힌트에 (3,1) , (3,2) 가 있는 것으로 보아 ,
  단순히 동시에 멘토 멘티 관계를 맺을 수 있는 모든 경우의 수만 count하면 된다고 생각하였다.
  

위의 모호한 점이 해결되자, 요구사항에 따른 해결 로직을 아래와 같이 생각하였다.

• 문제의 입력 예시를 기준으로 , a/b/c/d 의 4명의 학생이 있다고 가정하면
  a b c d
  3 4 1 2
  4 3 2 1
  2 4 1 3
• 1. 위와 같이 각 테스트에 대한 , 각 학생별 등수를 기록한다
• 2. 각 학생이 멘토일 경우를 가정하여 - 문제에서 주어진 조건을 만족하는 횟수를 count한다.
  a가 멘토일 경우
  -> (a,b) (a,c) (a,d) 경우에 대해 , M번에 걸친 테스트 결과 비교
  b가 멘토일 경우
  -> (b,a) (b,c) (b,c) 경우에 대해 , M번에 걸친 테스트 결과 비교
  c가 멘토일 경우
  -> (c,a) (c,b) (c,d) 경우에 대해 , M번에 걸친 테스트 결과 비교
  d가 멘토일 경우
  -> (d,a) (d,b) (d,c) 경우에 대해 , M번에 걸친 테스트 결과 비교

위 로직에 따른 세부적인 코드 구현에 대한 설명을 간략하게 덧붙이겠다.

1. 입력값에 대한 각 학생별 등수 기록 코드

• arr[M][N] 로 배열 사이즈를 잡지 않고 , arr[M][N+1]로 배열 사이즈를 잡는다
• 그러면 0번 컬럼을 사용하지 않으면 ,
  1번컬럼부터 1번학생이라고 간주하여 1번 컬럼부터 N번 컬럼까지를 각 학생으로 간주할 수 있다.
• 그렇게 했을 때 - 가장 먼저 입력된 등수가 3이라면 , 0번째 테스트에서 3번 학생이 1등이라는 의미 이므로
• arr[M][3] = rank++ (rank는 1로 초기화) 식으로
  각 테스트에 대한 - 각 학생별 등수를 배열에 저장할 수 있다.

2. 각 학생별로 멘토를 가정하고 - 나머지 학생들을 각각 멘티라고 가정했을 때 - M번의 수학테스트 등수를 비교하여 (멘토 등수 < 멘티 등수) 조건을 만족하는지 비교

• 처음에는 이 로직을 2중 for문으로 해결할 수 있을 거라고 생각했다.
• 그런데 각 학생별 경우의 수를 만들 때 이미 2중 for문이 되고, 각 경우 별로 M번의 수학 테스트 결과를 봐야 하니 - 결과적으로 3중 for문이 필요하였다.
• 일단 각 학생별로 멘토가 되고 - 나머지 학생들이 멘티가 되는 경우는
  아래와 같은 이중 for문으로 구현할 수 있었다.

for(int i=1; i<=N; i++){
	for(int j=1; j<=N; j++){
    	if(i==j) continue;
    }
}

• 이후 이 2중for문 안에서 , 다시한번 for문을 써서 M번의 수학테스트 등수를 비교하면 되었다.
  즉 아래의 for문이 위 2중for문 안에 들어가도록 하였다.

//flag는 1로 초기화 / cnt는 0으로 초기화
for(int k=0; k<M; k++){
	if(arr[k][i] > arr[k][j]){
    	flag = 0;
        break;
    }
}
if(flag == 0) 	flag = 1; // 모든 테스트에서 멘토 등수가 더 낮지는 x
else			cnt++; // 조건을 만족하는 case

위와 같은 로직에 기반하여 작성한 코드는 결과적으로 아래의 코드이다.

package section2.question12;

import java.util.Scanner;

public class Main {

public static int solution(int[][] arr, int N, int M){

   int cnt = 0;
   int flag = 1;

   for(int i=1; i<=N; i++){
       for(int j=1; j<=N; j++){
           if(i==j) continue;
           for(int k=0; k<M; k++){
               if(arr[k][i] > arr[k][j]){
                   flag = 0;
                   break;
               }
           }
           if(flag == 1)
               cnt++;
           else
               flag = 1;
       }
   }

   return cnt;
}

public static void main(String[] args) {

    //0. Scanner 준비
    Scanner sc = new Scanner(System.in);

    //1. 입력
    int N = sc.nextInt();
    int M = sc.nextInt();

    int[][] arr = new int[M][N+1];
    int idx = 0;
    int rank = 1;

    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            idx = sc.nextInt();
            arr[i][idx] = rank++;
        }
        rank = 1;
    }

    //2. solution() 호출
    int result = solution(arr, N, M);

    //3. 그에 따른 결과 출력
    System.out.println(result);

}

}