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

백준 16165 걸그룹 마스터 준석이

[Silver III] 걸그룹 마스터 준석이 - 16165

문제 링크

성능 요약

메모리: 11440 KB, 시간: 76 ms

분류

자료 구조(data_structures), 해시를 사용한 집합과 맵(hash_set)

문제 설명

정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 퀴즈 프로그램을 만들고자 한다.

입력

첫 번째 줄에는 총 입력 받을 걸그룹의 수 N(0 < N < 100)과 맞혀야 할 문제의 수 M(0 < M < 100)을 입력받는다.

두 번째 줄부터는 각 걸그룹마다 팀의 이름, 걸그룹의 인원 수, 멤버의 이름을 한 줄씩 차례대로 입력받는다. 팀과 멤버의 이름은 최대 100글자이며, 모든 글자는 알파벳 소문자이다. 하나의 걸그룹이나 서로 다른 두 걸그룹에 이름이 같은 두 멤버가 있는 경우는 없다.

그 다음 줄부터는 M개의 퀴즈를 입력받는다. 각각의 퀴즈는 두 줄로 이루어져 있으며, 팀의 이름이나 멤버의 이름이 첫 줄에 주어지고 퀴즈의 종류를 나타내는 0 또는 1이 두 번째 줄에 주어진다. 퀴즈의 종류가 0일 경우 팀의 이름이 주어지며, 1일 경우 멤버의 이름이 주어진다.

출력

첫 번째 줄부터 차례대로 퀴즈에 대한 답을 출력한다. 퀴즈의 종류가 0일 경우 해당 팀에 속한 멤버의 이름을 사전순으로 한 줄에 한 명씩 출력한다. 퀴즈의 종류가 1일 경우 해당 멤버가 속한 팀의 이름을 출력한다.

---

알고리즘 과정

먼저 생각했던 것은 각 팀이 있고 그 팀에 소속된 멤버들이 있는 문제이니 HashMap을 사용해야겠다고 생각했다.

그 HashMap에는 물론 팀이 Key값 멤버들이 Value 값으로 들어가야 하는데 중복된 키 값을 가질 수 없으므로 Value값은 자동으로 배열을 사용하게 될 것이다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder();
HashMap<String, String[]> hashMap = new HashMap<>();

이제 팀 이름, 멤버 수, 멤버의 각자 이름을 저장해주어야 한다.

팀 이름 Key, 팀 멤버 Value로 저장을 하는데 Value값이 배열로 되어 있으므로 배열안에 모두 저장을 하고 그 배열을 직접 맵에 넣어주면 된다. (넣어주기 전에 사전순 배열로 멤버를 정렬 후 넣어주자.)

while(N-->0){
    String team = br.readLine();
    int teamNum = Integer.parseInt(br.readLine());
    String[] member = new String[teamNum];
    for (int i = 0; i < teamNum; i++) {
        member[i] = br.readLine();
    }
    Arrays.sort(member);
    hashMap.put(team, member);
}

이제 정답을 도출할 차례이다. 여기서 좀 고민했던 점이 있다.

해쉬 맵은 벨류값으로 키값을 가져오는 것이 원래는 불가능하다. 그럼 어떻게 멤버의 이름으로 그룹의 이름을 알 수 있을까?

생각해낸 방법은 조금 복잡하지만 이렇다. HashMap의 keySet을 이용하는 방법이다.

1. 먼저 keySet으로 해쉬맵의 모든 키 값을 하나 하나 꺼낸다.
2. 그 키 값으로 벨류값을 하나 하나 꺼낸다.
3. 꺼낸 벨류 값으로 찾으려는 멤버 이름과 비교한 후 맞다면 키 값(=그룹이름)을 출력한다.

while(M-->0){
    String tmp = br.readLine();
    int k = Integer.parseInt(br.readLine());
    if(k == 0){
        for (String s : hashMap.get(tmp)){
            sb.append(s).append('\n');
        }
    }
    else if(k == 1){
        for (String key : hashMap.keySet()){
            for (String value : hashMap.get(key)) {
                if(value.equals(tmp)){
                    sb.append(key).append('\n');
                }
            }
        }
    }
}

---

전체 코드