[25325] 학생 인기도 측정

[Silver V] 학생 인기도 측정 - 25325

문제 링크

성능 요약

메모리: 16896 KB, 시간: 208 ms

분류

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

문제 설명

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

입력

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

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

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

출력

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

아이디어

학생별 인기도를 Map으로 관리한다.
keySet을 이용하여 value를 기준으로 Map을 정렬할 수 있다는 것이 인상적이었다.

답안코드

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

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

        // 학생 수
        int n = Integer.parseInt(br.readLine());

        // 학생 목록
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 학생 별 인기도 Map
        Map<String, Integer> students = new HashMap<>();
        for (int i = 0; i < n; i++) {
            students.put(st.nextToken(), 0);
        }

        // 학생 별로 인기도 조사
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            while (st.hasMoreTokens()) {
                String student = st.nextToken();
                students.put(student, students.get(student) + 1);
            }
        }

        // key List를 value를 기준으로 정렬
        List<String> keyList = new ArrayList<>(students.keySet());

        keyList.sort((k1, k2) -> {
            if (students.get(k1) - students.get(k2) == 0)
                return k1.compareTo(k2);
            return students.get(k2) - students.get(k1);
        });

        // value 기준으로 정렬한대로 결과 출력
        keyList.forEach(k -> System.out.println(k + " " + students.get(k)));
    }
}

BOJ 카테고리 내 다른 글 보러가기