섹션 2. Array - 12. 멘토링

📌 문제 설명

M번의 수학 테스트 결과를 바탕으로 멘토와 멘티 쌍을 만들 수 있는 경우의 수를 구하는 문제입니다.

• 멘토(A)는 모든 테스트에서 멘티(B)보다 등수가 앞서야 합니다.
• 각 테스트의 결과는 등수 순서대로 학생 번호가 주어집니다.

---

📝 입력 & 출력

입력

• 첫 줄: 학생 수 N(1 ≤ N ≤ 20), 테스트 수 M(1 ≤ M ≤ 10)
• 이후 M줄: 각 줄에 테스트 결과가 등수 순으로 나열된 학생 번호

출력

• 멘토-멘티 쌍을 만들 수 있는 총 경우의 수

---

🔸 예제 입력 & 출력

예제 입력 1

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

 

예제 출력 1

3

---

💡 해결 방법

• 학생 A와 B를 모든 쌍에 대해 순회하며 비교합니다.
• 모든 테스트에서 A가 B보다 앞 순위에 있으면 유효한 멘토-멘티 쌍으로 간주합니다.

---

💻 코드 구현 (Java)

package partArray;

import java.util.*;

public class Problem12 {
	public int solution(int n, int m, int[][] arr) {
		int answer = 0;

		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i == j) continue;
				boolean flag = true;
				for(int k = 0; k < m; k++) {
					int pi = -1, pj = -1;
					for(int l = 0; l < n; l++) {
						if(arr[k][l] == i) pi = l;
						if(arr[k][l] == j) pj = l;
					}
					if(pi > pj) {
						flag = false;
						break;
					}
				}
				if(flag) answer++;
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Problem12 T = new Problem12();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[][] arr = new int[m][n];
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				arr[i][j] = kb.nextInt();
			}
		}
		System.out.print(T.solution(n, m, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 학생 쌍 (i, j) 반복

• i: 멘토 후보, j: 멘티 후보
• i ≠ j 인 경우만 확인

2️⃣ 테스트마다 등수 비교

int pi = -1, pj = -1;
for (int l = 0; l < n; l++) {
	if (arr[k][l] == i) pi = l;
	if (arr[k][l] == j) pj = l;
}

• pi < pj이어야 멘토 조건 충족 (등수가 낮을수록 잘한 것)

3️⃣ 모든 테스트에서 i가 j보다 앞서면 쌍 추가

if (flag) answer++;

---

⏳ 시간 복잡도 분석

• 3중 반복문 사용 → O(N² × M × N)
  → 하지만 최대 N=20, M=10이므로 완전탐색 가능

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런