[99클럽 코테스터디 TIL 19일차] 백준 25325번 학생 인기도 측정 해설 및 풀이 (Java)

백준 25325번 학생 인기도 측정

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

---

문제

 

학생 이름이 공백으로 구분된 문자열 A가 주어진다. 문자열 A에는 중복된 학생 이름이 존재하지 않는다. 학생 이름은 알파벳 소문자로 이루어져 있다. 각 학생이 좋아하는 학생의 학생 이름 목록이 공백으로 구분된 문자열로 주어진다. 각 학생이 좋아하는 학생은 1명 이상 주어지고, 내가 나를 좋아하는 예는 없다. 나를 좋아하는 학생이 많을수록 나의 인기도가 높다. 인기도가 높은 학생부터 낮은 학생 순으로 학생 이름과 해당 학생을 좋아하는 학생 수를 출력하자. 인기도가 같은 경우 학생 이름 기준으로 오름차순으로 출력하자.

입력

첫 번째 줄에 학생 수 n이 주어진다.

두 번째 줄에 n명의 학생 이름이 공백으로 구분된 문자열 A가 주어진다.

다음 줄부터 n개의 줄에 걸쳐 한 줄에 한 학생의 정보가 주어진다. 학생 정보는 문자열 A에 나온 학생 순서대로 주어진다. 한 명의 학생 정보는 해당 학생이 좋아하는 학생 이름이 공백으로 구분된 문자열로 주어진다.

출력

첫 번째 줄부터 n번째 줄까지 학생 이름과 해당 학생을 좋아하는 학생 수를 공백으로 구분하여 한 줄에 출력한다. 인기도가 높은 학생부터 낮은 학생 순으로 출력하고, 인기도가 같은 경우 학생 이름 기준으로 오름차순으로 출력한다.

제한

• 3 ≤ n ≤ 100
• 1 ≤ 학생 이름 길이 ≤ 10

---

문제 유형

자료 구조 문자열 정렬 해시를 사용한 집합과 맵 트리를 사용한 집합과 맵

 

풀이 방법 도출

 

총 n명의 학생이 있으며 각 학생이 좋아하는 다른 학생들의 이름을 나열합니다.

나를 좋아하는 학생 수는 인기도 점수입니다.

인기도 점수를 계산한 후 인기도 순으로 내림차순으로 정렬합니다.

만약 인기도 점수가 같다면 이름 오름차순으로 정렬하여 출력합니다.

 

1. 학생 이름을 배열 List<String> 로 저장합니다.
2. 각 학생이 좋아하는 학생 목록을 받아온 후, 좋아하는 대상 학생의 인기도 점수를 증가시킵니다.
3. HashMap<String, Integer> 를 사용하여 학생별로 인기도 점수를 저장합니다.
4. Entry 리스트를 인기도 내림차순 정렬합니다. 인기도가 같으면 이름 오름차순으로 정렬합니다.

 

 

시간 복잡도

• 입력 처리: O(n²)
• 정렬: O(n log n)
• 최종 출력: O(n)
• 총 시간 복잡도: O(n²)

---

핵심 코드 삽입 및 설명

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

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()); // 학생 수 입력

        Map<String, Integer> popularity = new HashMap<>(); // 인기도 저장용
        String[] names = br.readLine().split(" "); // 학생 이름 리스트

        // 모든 학생 이름을 초기화
        for (String name : names) {
            popularity.put(name, 0);
        }

        // 각 학생이 좋아하는 학생 정보 입력 처리
        for (int i = 0; i < n; i++) {
            String[] likes = br.readLine().split(" "); // 현재 학생이 좋아하는 사람들

            for (String like : likes) {
                // 좋아하는 학생의 인기도 점수를 1 증가
                popularity.put(like, popularity.get(like) + 1);
            }
        }

        // popularity Map을 정렬하기 위해 entrySet을 리스트로 변환
        List<Map.Entry<String, Integer>> list = new ArrayList<>(popularity.entrySet());

        // 인기도 점수로 내림차순 정렬
        // 인기도 점수가 같으면 이름으로 오름차순 정렬
        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o2.getValue().equals(o1.getValue())) {
                    return o1.getKey().compareTo(o2.getKey());
                }
                return o2.getValue() - o1.getValue();
            }
        });

        // 출력
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> entry : list) {
            sb.append(entry.getKey()).append(" ").append(entry.getValue()).append("\n");
        }
        System.out.print(sb.toString());
    }
}