[백준 JAVA] 16165 걸그룹 마스터 준석이

16165 걸그룹 마스터 준석이

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

문제설명

1. 팀 이름을 주면 해당 팀의 멤버들을 오름차순으로 정렬하여 출력한다.
2. 멤버 이름을 주면 그 멤버가 속한 팀의 이름을 출력한다.

각 팀은 여러 멤버를 가질 수 있으며, 멤버는 오직 하나의 팀에만 속할 수 있다.

접근방식

O(N * M + M * log M) 시간복잡도

•  N은 팀의 수, M은 각 팀의 평균 멤버 수만큼 O(N * M)를 입력받는다.
• 각 팀의 멤버를 정렬하면 O(M * log M) 시간복잡도가 소요된다.
• O(M) M은 쿼리의 수이다.

문제 조건 분석 과정

 

• 입력:
  • 첫 줄에서 팀의 수 NNN과 쿼리의 수 MMM을 입력받는다.
  • 각 팀의 정보 (팀 이름과 팀 멤버 수), 그리고 팀의 멤버 이름을 입력받는다.
  • 각 쿼리는 팀 이름 또는 멤버 이름과 쿼리 유형(0 또는 1)을 포함한다.
• 데이터 구조:
  • HashMap<String, ArrayList<String>>: 팀 이름을 키로, 해당 팀의 멤버 목록을 값으로 저장한다.
  • HashMap<String, String>: 멤버 이름을 키로, 해당 멤버가 속한 팀 이름을 값으로 저장한다.
• 쿼리 처리:
  • 쿼리 유형이 0인 경우: 주어진 팀 이름으로 팀의 멤버 목록을 가져와 정렬한 후 출력한다.
  • 쿼리 유형이 1인 경우: 주어진 멤버 이름으로 해당 멤버가 속한 팀의 이름을 가져와 출력한다.

 

전체코드

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));

        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken()); //팀의 수
        int m = Integer.parseInt(st.nextToken()); //멤버 이름

        //key: 팀 이름 value: 팀 멤버 리스트
        HashMap<String, ArrayList<String>> mem = new HashMap<>();
        //key: 멤버 이름 value: 팀 이름
        HashMap<String, String> team = new HashMap<>();

        //팀 정보 입력
        for (int i = 0; i < n; i++) {

            ArrayList<String> members = new ArrayList<>();

            //팀 이름
            String teamName = br.readLine();
            //팀 멤버 수
            int memberCount = Integer.parseInt(br.readLine());

            //각 팀의 멤버를 members list에 추가하여 team맵에 멤버와 팀 매핑
            for (int j = 0; j < memberCount; j++) {
                String memberName = br.readLine();
                members.add(memberName);
                team.put(memberName, teamName); // 멤버와 팀 매핑
            }
            //key: 팀 이름 value: 멤버 리스트 에 저장
            mem.put(teamName, members); // 팀과 멤버 매핑
        }

        for (int i = 0; i < m; i++) {
            String query = br.readLine();
            String type = br.readLine();

            //쿼리가 0인 경우: 팀 멤버를 정렬하여 출력
            if (type.equals("0")) {
                //key: 팀 이름
                ArrayList<String> members = mem.get(query);
                //멤버 리스트를 오름차순으로 정렬
                Collections.sort(members);
                //정렬된 멤버 리스트를 sb에 추가
                for (String member : members) {
                    sb.append(member).append("\n");
                }
                //1인 경우 멤버의 소속팀 출력
            } else if (type.equals("1")) {
                //멤버 이름을 키로 사용
                sb.append(team.get(query)).append("\n");
            }
        }

        System.out.print(sb);
    }
}