[Array] 임시반장 정하기

김우진·2022년 7월 18일

algorithm array infrean

알고리즘 문제

목록 보기

13/21

임시반장 정하기

문제 정보

사이트 : Infrean 자바 알고리즘 문제 풀이 강의
문제 번호 : 2강 11번
문제 분류 : Array

문제 풀이

내가 짠 코드

n이 동적이라 ArrayList를 이용하였다.
학생 수가 주어지면 그 개수 만큼 배열을 만들고 각 학생의 1학년 부터 5학년 까지의 반 기록을 저장하였다.
그 후 한 학생을 기준으로 같은 반이 었던 학생을 찾고 찾으면 그 학생에 대한 check 배열을 true로 변경해 같은 학생에 대한 count증가를 막았다.
count 값이 max 값보다 크면 임시반장이 될 수 있으므로 result 값과 max 값을 변경시켰다.
번호가 빠른 학생 기준으로 result를 변경시키기에 여러 명의 count 값이 같아도 제일 빠른 번호가 임시반장이 된다.

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

public class 임시반장_정하기 {
    private static ArrayList<int[]> classmates = new ArrayList<>();
    private static int max = 0;
    private static int result = 1;

    public static void checkLeader(int[] classmate, int n, int classmateIndex){
        boolean[] check = new boolean[n];
        int count = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < n; j++) {
                if(check[j] || j == classmateIndex)
                    continue;
                if(classmates.get(j)[i] == classmate[i]) {
                    check[j] = true;
                    count++;
                }
            }
        }
        if(max < count){
            max = count;
            result = classmateIndex + 1;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int[] classmate = new int[5];
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < 5; j++) {
                classmate[j] = Integer.parseInt(input[j]);
            }
            classmates.add(classmate);
        }

        for (int i = 0; i < n; i++) {
            checkLeader(classmates.get(i), n, i);
        }

        System.out.println(result);
        br.close();
    }
}

정답 코드

2중 배열을 이용하였다.
n 값이 정해지므로 int[][] arr = new int[n][5];로 배열을 선언하여 풀었다.
시간 복잡도 상으론 둘다 O(n^2)으로 똑같을 거 같긴하다.

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

public class 임시반장_정하기 {
    public static int solution(int n, int[][] arr){
        int result = 0, max = Integer.MIN_VALUE;
        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(count > max){
                max = count;
                result = i+1;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][5];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < 5; j++) {
                arr[i][j] = Integer.parseInt(input[j]);
            }
        }
        System.out.println(solution(n, arr));
        br.close();
    }
}