[JAVA] 백준_1268 임시 반장 정하기

https://www.acmicpc.net/problem/1268

📌 문제 탐색하기

각 학생이 다른 학생들 중 몇명과 같은 반을 한 적이 있는지 횟수를 구하는 문제이다. 

📌 코드 설계하기 & 가능한 시간복잡도

- 입력하기 ( 시간복잡도 : O(N) ) 
numberOfStudents 명을 입력받기 -> 각 학생별로 1학년 ~ 5학년 동안 어떤 반에 속했는지 classInfo 2차원 배열에 저장 
- 비교 - count ++ ; ( 시간복잡도 : O(N^2) ) 
각 학년별로 순회하면서 각 학년에 대해서 모든 학생의 쌍을 비교해서 같은반과 번호인 경우 true으로 저장 -> true인 학생의 수를 count하기 
- 가장 친구수가 많은 학생을 찾아서 출력한다.  ( 시간복잡도 : O(N) ) 

따라서 가능한 최종 시간복잡도는 O(N^2) 입니다. 

📌 정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numberOfStudents = Integer.parseInt(br.readLine());
        
        int[][] classInfo = new int[numberOfStudents][5];
        for (int student = 0; student < numberOfStudents; student++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int grade = 0; grade < 5; grade++) {
                classInfo[student][grade] = Integer.parseInt(st.nextToken());
            }
        }
        
        boolean[][] hasSharedClass = new boolean[numberOfStudents][numberOfStudents];

        // 같은 반이었던 경우
        for (int grade = 0; grade < 5; grade++) {
            for (int studentA = 0; studentA < numberOfStudents; studentA++) {
                for (int studentB = studentA + 1; studentB < numberOfStudents; studentB++) {
                    if (classInfo[studentA][grade] == classInfo[studentB][grade]) {
                        hasSharedClass[studentA][studentB] = true;
                        hasSharedClass[studentB][studentA] = true;
                    }
                }
            }
        }

        // 각 학생이 알고 있는 친구 수를 세기
        int[] friendsCount = new int[numberOfStudents];
        for (int studentA = 0; studentA < numberOfStudents; studentA++) {
            for (int studentB = 0; studentB < numberOfStudents; studentB++) {
                if (hasSharedClass[studentA][studentB] && studentA != studentB) {
                    friendsCount[studentA]++;
                }
            }
        }

        // 가장 많은 친구를 가진 학생 찾기
        int mostFriends = -1;
        int leaderStudent = -1;
        for (int student = 0; student < numberOfStudents; student++) {
            if (friendsCount[student] > mostFriends) {
                mostFriends = friendsCount[student];
                leaderStudent = student;
            }
        }

        // 학생 번호는 1번부터 시작하므로 +1 해서 출력
        System.out.println(leaderStudent + 1);
    }
}