섹션 2. Array - 11. 임시반장 정하기

📌 문제 설명

김갑동 선생님이 임시 반장을 정하려고 합니다. 임시 반장은 1학년부터 5학년까지 한번이라도 같은 반이었던 사람이 가장 많은 학생입니다.

학생 수와 각 학생의 1~5학년까지의 반 정보를 토대로 임시 반장을 정하세요.

---

📝 입력 & 출력

입력

• 첫째 줄에 학생 수(N, 3 ≤ N ≤ 1000)가 주어집니다.
• 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 1학년부터 5학년까지의 반 정보가 주어집니다.

출력

• 임시 반장으로 선정된 학생 번호를 출력합니다.
• 같은 반 학생 수가 같다면 번호가 작은 학생을 출력합니다.

---

🔸 예제 입력 & 출력

예제 입력 1

5
2 3 1 7 3
4 1 9 6 8
5 5 2 4 4
6 5 2 6 7
8 4 2 2 2

 

예제 출력 1

4

---

💡 해결 방법

• 모든 학생을 다른 모든 학생과 비교하여 같은 반을 했던 적이 있는지 확인합니다.
• 같은 반이었던 학생 수가 가장 많은 학생을 임시 반장으로 선정합니다.

---

💻 코드 구현 (Java)

package partArray;

import java.util.*;

public class Problem11 {
	public int solution(int n, int[][] arr) {
		int max = Integer.MIN_VALUE, answer = 0;
		for(int i = 0; i < n; i++) {
			int count = 0;
			for(int j = 0; j < n; j++) {
				for(int k = 0; k < 5; k++) {
					if(arr[i][k] == arr[j][k]) {
						count++;
						break;
					}
				}
			}
			if(max < count) {
				answer = i + 1;
				max = count;
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Problem11 T = new Problem11();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[][] arr = new int[n][6];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 5; j++) {
				arr[i][j] = kb.nextInt();
			}
		}
		System.out.print(T.solution(n, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 같은 반 학생 수 확인

for(int k = 0; k < 5; k++) {
	if(arr[i][k] == arr[j][k]) {
		count++;
		break;
	}
}

• 각 학생이 다른 학생과 1~5학년 중 한 번이라도 같은 반이었으면 카운트합니다.

2️⃣ 임시 반장 선정

if(max < count) {
	answer = i + 1;
	max = count;
}

• 같은 반이었던 학생 수가 가장 많을 때 그 학생 번호를 저장합니다.

---

⏳ 시간 복잡도 분석

• 학생 간 비교 횟수가 N명에 대해 최대 N×5번이므로, 시간 복잡도는 O(N²)입니다.

---

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

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