[백준 Baekjoon] 1268번 임시 반장 정하기 - JAVA

문제풀이

문제의 난이도는 브로즌 1이라지만, 체감은 더 난이도가 있었던것 같습니다. 풀기 엄청 귀찮은 문제였습니다.

int[][] arr = new int[5][N];

Set[] dupCheckSet = new Set[N];
int max = 0, answer = 1;

• 표는 나중에 계산하기 편하게 i를 학년으로 j를 학생으로 생성하고 저장하였습니다.
• 중복되는 학생을 검사하기 위해 set 배열을 사용하였습니다.
• 한 번도 겹치지 않는 경우 1번 학생이 정답이여 초기값을 1로 하였습니다.

for (int i = 0; i < 5; i++) {
    Map<Integer, List<Integer>> stuClsMap = new HashMap<>();

    for (int j = 0; j < N; j++) {
        List<Integer> value = stuClsMap.getOrDefault(arr[i][j], new ArrayList<>());
        value.add(j);

        stuClsMap.put(arr[i][j], value);
    }

    for (Entry<Integer, List<Integer>> entry : stuClsMap.entrySet()) {
        if (entry.getValue().size() > 1) {
            for (int stuN : entry.getValue()) {
                dupCheckSet[stuN].addAll(entry.getValue());
                dupCheckSet[stuN].remove(stuN);
            }
        }
    }
}

• 학생들의 반을 key로 학생을 value로 하여 저장합니다.
• 반의 학생이 2이상 있는 경우 같은 반인 학생이 있는 경우입니다.
• 같은 반의 학생들을 set에 추가합니다. 자신은 제외합니다.

for (int i = 0; i < N; i++) {
    if (dupCheckSet[i].size() > max) {
        max = dupCheckSet[i].size();
        answer = i + 1;
    }
}

• 가장 같은 반이었던 사람이 많은 학생을 찾습니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map.Entry;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[5][N];

        Set[] dupCheckSet = new Set[N];
        int max = 0, answer = 1;

        for (int j = 0; j < N; j++) {
            dupCheckSet[j] = new HashSet();

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

        for (int i = 0; i < 5; i++) {
            Map<Integer, List<Integer>> stuClsMap = new HashMap<>();

            for (int j = 0; j < N; j++) {
                List<Integer> value = stuClsMap.getOrDefault(arr[i][j], new ArrayList<>());
                value.add(j);

                stuClsMap.put(arr[i][j], value);
            }

            for (Entry<Integer, List<Integer>> entry : stuClsMap.entrySet()) {
                if (entry.getValue().size() > 1) {
                    for (int stuN : entry.getValue()) {
                        dupCheckSet[stuN].addAll(entry.getValue());
                        dupCheckSet[stuN].remove(stuN);
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            if (dupCheckSet[i].size() > max) {
                max = dupCheckSet[i].size();
                answer = i + 1;
            }
        }

        System.out.println(answer);
    }
}