[알고리즘] 2-11 임시반장 정하기 (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/02-11
• 문제 설명 : 학생 중에서 1학년부터 5학년까지 지내오면서 한 번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하는 문제.
• 입력 : 학생 숫자 n, n명의 학생이 1~5학년 각각 몇반이었는지
• 출력 : 같은 반이었던 사람이 가장 많은 학생의 번호

내 풀이

package inflearn.array;

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

public class Main2_11 {

    public static int solution(int n, int[][] arr) {
        int stuNum = -1; //학생 번호
        int max = -1; //같은 반이 된 최대 횟수

        for (int i = 0; i < n; i++) {
            //같은 친구와 여러 학년에 같은 반이 될 수 있기 때문에, 중복을 허용하지 않는 set 사용
            Set<Integer> set = new HashSet<>();

            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }

                for (int k = 0; k < 5; k++) {
                    if (arr[i][k] == arr[j][k]) {
                        set.add(j);
                    }
                }
            }

            if (set.size() > max) {
                max = set.size();
                stuNum = i+1;
            }
        }

        return stuNum;
    }

    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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; st.hasMoreTokens(); j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(solution(n, arr));
    }
}

강의 풀이

• 친구와 여러 학년 동안 같은 반이 될 수 있기 때문에 중복을 제거하기 위해 set 자료구조를 사용해서 풀이를 했었는데, 그냥 단지 최초 한번 같은 반이 되었을 때 count를 1 증가시키고, break 문을 걸면 굳이 나머지 루프를 돌지 않고 풀이할 수 있다.. 왜 이 생각을 못했지...ㅜ

public static int solution(int n, int[][] arr) {
    int stuNum = -1; //학생 번호
    int max = -1; //같은 반이 된 최대 횟수

    for (int i = 0; i < n; i++) {
        int count = 0;

        for (int j = 0; j < n; j++) {
            if (i == j) {
                continue;
            }

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

        if (count > max) {
            max = count;
            stuNum = i + 1;
        }

    }

    return stuNum;
}