[백준] 1268_임시반장정하기

 

 

Sliver

 

 

문제

 

오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다.

오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다.

그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다.

그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다.

예를 들어 학생 수가 5명일 때의 표를 살펴보자.

	1학년	2학년	3학년	4학년	5학년
1번 학생	2	3	1	7	3
2번 학생	4	1	9	6	8
3번 학생	5	5	2	4	4
4번 학생	6	5	2	6	7
5번 학생	8	4	2	2	2

 

위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도 같은 반이었던 사람은 2번 학생, 3번 학생과 5번 학생으로 모두 3명이다. 이 예에서 4번 학생이 전체 학생 중에서 같은 반이었던 학생 수가 제일 많으므로 임시 반장이 된다.

각 학생들이 1학년부터 5학년까지 속했던 반이 주어질 때, 임시 반장을 정하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에는 반의 학생 수를 나타내는 정수가 주어진다.

학생 수는 3 이상 1000 이하이다.

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

주어지는 정수는 모두 1 이상 9 이하의 정수이다.

 

 

출력

 

첫 줄에 임시 반장으로 정해진 학생의 번호를 출력한다.

단, 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그 중 가장 작은 번호만 출력한다.

 

 

---

 

풀이 1 - Map

 

import java.util.*;
import java.io.*;

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[][] classes = new int[n+1][5+1];
        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=5; j++){
                classes[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Map<Integer, Integer> student = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                for (int year = 1; year <= 5; year++) {
                    if (classes[i][year] == classes[j][year]) {
                        student.put(i, student.getOrDefault(i, 0) + 1);
                        break; // 한 해에 같은 반이라면 더 비교하지 않아도 됨
                    }
                }
            }
        }

        if(student.size() == 0){
            System.out.println(1);
            return; 
        }
        
        List<Integer> keys = new ArrayList<>(student.keySet());
        Collections.sort(keys, (o1, o2) -> {
            if(student.get(o1).equals(student.get(o2)))
                return o1 - o2; 
            return student.get(o2) - student.get(o1);
        });
        
        System.out.println(keys.get(0));
    }
}

 

 

 

해결방법

• 입력받은 n과 각 학생의 학년별 반 번호를 2차원 배열 classes에 저장한다.
   -> classes[i][j]는 i번째 학생의 j학년 반 번호를 의미
• 각 학생에 대해 다른 모든 학생과 학년별로 반 번호를 비교한다.
  1. 현재 학생과 비교 대상 학생이 같은 반이었던 적이 있는 경우, 현재 학생의 카운트를 증가시킨다.
  2. Map을 사용하여 학생 번호를 키로, 같은 반이었던 횟수를 값으로 저장한다.
• 이 Map을 값 기준으로 내림차순 정렬한 후, 가장 첫 번째로 오는 학생 번호가 임시 반장이 된다.

 

 

 

 

풀이2_Set

 

import java.util.*;
import java.io.*;

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[][] classes = new int[n+1][5+1];
        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=5; j++){
                classes[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int max = 0;
        int result = 1;
        for (int i = 1; i <= n; i++) {
            Set<Integer> student = new HashSet<>();
            for (int year = 1; year <= 5; year++) {
                for (int j = 1; j <= n; j++) {
                    if(i==j) continue;
                    if (classes[i][year] == classes[j][year]) {
                        student.add(j);
                    }
                }
            }
            if(student.size()>max){
                max = student.size();
                result = i;
            }
        }
        
        System.out.println(result);
    }
}

 

데이터를 저장한 후 따로 정렬이 필요하지 않다.

학생은 모두 독립적인 데이터이기 때문에 자료구조 Set을 활용할 수 있었다. 

 

해결방법

• 입력받은 n과 각 학생의 학년별 반 번호를 2차원 배열 classes에 저장한다.
   -> classes[i][j]는 i번째 학생의 j학년 반 번호를 의미
• 각 학생에 대해 다른 모든 학생과 학년별로 반 번호를 비교한다.
  1. 현재 학생과 비교 대상 학생이 같은 반이었던 적이 있는 경우, 자료구조 Set에 해당 학생을 추가한다. 
     이후 한번 더 같은 반이 되었다고 하더라도, Set은 자동으로 중복을 제거하여 중복 없이 저장할 수 있다. 
  2. Set의 사이즈가 (같은 반이었던 학생의 수) max보다 클 경우 max값을 업데이트하고, result에 현재 학생을 저장한다. 
• 최종으로 result에 남게 된 학생이 임시반장이 된다. 

 

 

 

 

 

 

---

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