[백준] | JAVA, 자바 | 1268번 - 임시 반장 정하기

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

1268번: 임시 반장 정하기

---

문제 요약 :

첫째 줄에는 반의 학생 수를 나타내는 정수가 주어진다. 학생 수는 3 이상 1000 이하이다. 둘째 줄부터는 1번 학생부터 차례대로 각 줄마다 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 5개의 정수가 빈칸 하나를 사이에 두고 주어진다. 주어지는 정수는 모두 1 이상 9 이하의 정수이다.

( 첫 줄에 임시 반장으로 정해진 학생의 번호를 출력한다. 단, 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그 중 가장 작은 번호만 출력 )

---

문제 풀이 :

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] student = new int[n][5];
        boolean[][] check = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                student[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[] classmate = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 5; k++) {
                    if (i == j) continue;
                    if (student[i][k] == student[j][k] && !check[i][j]) {
                        classmate[i]++;
                        check[i][j] = true;
                    }
                }
            }
        }

        int classMateMax = 0;
        int result = -1;

        for (int i = 0; i < n; i++) {
            if (classmate[i] > classMateMax) {
                classMateMax = classmate[i];
                result = i;
            }
            if (classMateMax == 0) {
                result = 0;
            }
        }
        System.out.println(result + 1);
    }
}

 

1. 반의 학생 수 n 입력받기

2. 학생들의 반을 저장할 2차원 배열 student 생성, 중복 값을 확인할 2차원 배열 check 생성

3. 학생 수만큼 1~5학년 반 입력받기

4. 같은 반이던 횟수를 확인하기 위해 배열 classmate  생성

5. for문을 통해 같은 반이었던 경우 확인, 같은 반일 경우 check 값을 true로 변경해 중복을 제거함

6. 전체 학생 중에서 같은 반이었던 학생 수가 제일 많은 경우를 구하기 위해 변수 classMateMax, result 생성

7. classmate[i]가 classMateMax 보다 값이 크다면 classMateMax 값을 classmate[i] 값으로 변경해 주고 result에 i 값을 저장

8. 만약 classMateMax가 0인 경우 (같은 반이었던 학생이 한명도 없었을 경우) result 값을 0으로 변경

9. result 값에 +1을 해주고 출력

 

처음 문제를 풀 때 마지막에 존재하는 if (classMateMax == 0) {result = 0;} 이 코드가 없어서 문제를 틀렸었다.

문제에서 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그중 가장 작은 번호만 출력이라는 조건은 있었지만 같은 반이었던 학생이 한 명도 없는 경우는 조건에 없었기에 생각을 안 하고 있었던 것이다.

그래서 마지막에 저 코드를 추가하고 같은 반이었던 학생이 한 명도 없을 경우 1번 학생이 임시 반장이 되도록 출력하게 만들자 문제의 정답을 맞힐 수 있었다.

---

HashSet 사용

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 Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] student = new int[n][5];
        int classMateMax = 0;
        int result = 0;

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 5; j++) {
                student[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < n; i++) {
            Set<Integer> check = new HashSet<>();
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < 5; k++) {
                    if(student[i][k] == student[j][k] && i != j) {
                        check.add(j);
                    }
                }
            }

            if(classMateMax < check.size()) {
                classMateMax = check.size();
                result = i;
            }
        }
        System.out.println(result + 1);
    }
}

 

HashSet으로 중복제거가 가능해서 HashSet을 사용한 코드

 

위 16812KB, 204ms for문과 Boolean 사용

밑 132316KB, 356ms HashSet 사용