[BaekJoon 16165번] 걸그룹 마스터 준석이(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 
 

[문제 풀이 사이트]

 
 

16165번: 걸그룹 마스터 준석이

 
 

[문제 설명]

 
 

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

 

[입력]

 
 

첫 번째 줄에는 총 입력 받을 걸그룹의 수 N(0 < N < 100)과 맞혀야 할 문제의 수 M(0 < M < 100)을 입력받는다.
두 번째 줄부터는 각 걸그룹마다 팀의 이름, 걸그룹의 인원 수, 멤버의 이름을 한 줄씩 차례대로 입력받는다. 팀과 멤버의 이름은 최대 100글자이며, 모든 글자는 알파벳 소문자이다. 하나의 걸그룹이나 서로 다른 두 걸그룹에 이름이 같은 두 멤버가 있는 경우는 없다.
그 다음 줄부터는 M개의 퀴즈를 입력받는다. 각각의 퀴즈는 두 줄로 이루어져 있으며, 팀의 이름이나 멤버의 이름이 첫 줄에 주어지고 퀴즈의 종류를 나타내는 0 또는 1이 두 번째 줄에 주어진다. 퀴즈의 종류가 0일 경우 팀의 이름이 주어지며, 1일 경우 멤버의 이름이 주어진다.

 
 
 

[출력]

 
 

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

 
 

[입출력 예]

 
 

입력	출력
3 4 twice 9 jihyo dahyeon mina momo chaeyoung jeongyeon tzuyu sana nayeon blackpink 4 jisu lisa rose jenny redvelvet 5 wendy irene seulgi yeri joy sana 1 wendy 1 twice 0 rose 1	twice redvelvet chaeyoung dahyeon jeongyeon jihyo mina momo nayeon sana tzuyu blackpink

 
 

[문제 풀이]

 
 

'해시'로 분류되는 문제이다.
보통 해시로 분류되면 map을 사용한다.
 
그리고 '걸그룹 마스터 준석이' 문제의 요점은
퀴즈의 종류가 0일 때는 팀의 이름이 주어지면 팀에 속한 멤버들을 사전순으로 출력해야하고
퀴즈의 종류가 1일 때는 멤버의 이름이 주어지면 해당 멤버가 어느 팀에 속해있는지 출력해야한다.
 
그래서 입력을 받을 때 퀴즈의 종류가 0일 때

• key의 중복을 허용하는 multimap을 사용
• key는 그룹명 value는 멤버명

 
퀴즈의 종류가 1일 때는

• map을 사용
• key는 멤버명 value는 그룹명

 

형태로 각 multimap과 map에 데이터를 저장하도록 했다.

 

이후 퀴즈의 종류의 입력이 주어질 때
0인 경우 팀의 이름이 주어졌을 때 팀에 속한 멤버들을 사전 순으로 출력하기 위해
multimap 자료 구조에서 vector로 변경하고 sort 함수를 사용하여 사전순으로 멤버들을 정렬하여 출력하도록 했다.
 
1인 경우 기존 map 자료 구조에서 멤버명(key)에 해당하는 value(그룹명)만 출력하도록 했다.

 

 

[최종 코드]

 
 

[GitHub]

 
 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 
 

#include <bits/stdc++.h>
using namespace std;
multimap<string, string> total_group[101]; // group, name
map<string, string> totalmember;// name, group

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M; // 걸그룹 수, 맞춰야할 문제 수
    int totalgirlNum = 0;
    for(int i = 0; i < N; ++i) {
        multimap<string, string> temp;
        string girlgroupName; cin >> girlgroupName;
        int girlNum; cin >> girlNum;
        totalgirlNum += girlNum;
        for(int j = 0; j < girlNum; ++j) {
            string name; cin >> name;
            temp.insert({girlgroupName, name});
            totalmember[name] = girlgroupName;
        }
        total_group[i] = temp;
    }

    for(int i = 0; i < M; ++i) {
        string str; 
        int kind; 
        cin >> str >> kind;
        if(kind == 0) {
            // str : 팀 이름
            for(int j = 0; j < N; ++j) {
                multimap<string, string> m = total_group[j];
                if(m.find(str) != m.end()) {
                    vector<string> v;
                    for(auto iter = m.begin(); iter != m.end(); ++iter) {
                        // 팀 전체 인원 출력 (사전 순)
                        v.emplace_back(iter->second);
                    }
                    sort(v.begin(), v.end());
                    for(string element : v) {
                        cout << element << '\n';
                    }
                    break;
                }
            }
        } else {
            // kind == 1, str : 멤버 이름
            cout << totalmember[str] << '\n';
        }
    }

    return 0;
}