[백준][알고리즘][C++] 16165 걸그룹 마스터 준석이

문제의 난이도

문제의 난이도 : Silver 2

문제 분석

이 문제는 필자가 출제 했던 문제다.

문제를 낼 당시에는 학부 2학년이었기 때문에 알고리즘에 대해서도 잘 몰랐고,

문제를 많이 풀어 보지 못 해서 여러모로 잘 냈다고 할 수 없는 문제라고 할 수 있다..

아무튼, 결론적으로 이 문제의 핵심은 다음과 같다.

1. 주어진 그룹과 멤버를 어떤 형식으로 저장할 것인가?
2. 출력을 위해서 어떤 형식이 좋은 저장 방식 일까?

즉, 두 질문 모두 어떤 자료 구조를 선택할 지가 초점이라고 할 수 있다.

문제 해결

Map을 쓰자!

원래 문제를 낸 의도는 이진 탐색 트리를 이용하는 방향이었다.

그러나, 시간이 지나고 나서 문제를 풀어 보니 이진 탐색 트리를 구현하기 보다 map을 써서 푸는 것이 더 편리하다는 것을 깨달았다.

걸그룹의 경우는 그룹의 이름을 key로 하고 그룹 멤버들 넣은 vector를 value로 하며,

멤버들의 경우는 이름을 key로 하고 그룹의 이름을 value로 한다.

이런 방식으로 구성하게 될 경우,

걸 그룹 이름이 나왔을 때 멤버 전부를 쉽게 출력할 수 있고 반대의 경우도 쉽다.

다만 공간을 덜 차지할 수 있는 방법이 없을까 고민해 봤으나, 탐색에 드는 비용을 무시할 수 없을 것 같았다.

 

해답 코드

최대한 본인의 힘으로 풀어보시고 확인하시는 걸 추천합니다!

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int main() {
    int N, M;
    vector<string>::iterator iter;
    
    // Group의 이름을 담을 변수
    string gName;
    
    // Group : Member vector 형태의 map
    map<string, vector<string>> group;
    
    // member 이름 : Group 이름 형태의 map
    map<string, string> member;

    cin >> N;
    cin >> M;
    
    // Group, Member의 이름을 키로 하는 map을 만드는 과정
    for (int i=0; i< N; i++) {
        int num;
        string name;
        vector<string> mem;
        cin >> gName >> num;

        for(int j=0; j< num; j++) {
            cin >> name;
            mem.push_back(name);
            member.insert(make_pair(name, gName));
        }
        sort(mem.begin(), mem.end());
        group.insert(make_pair(gName, mem));
    }
	
    // 문제 타입(그룹의 이름이 주어졌는지, 멤버의 이름이 주어졌는지)에 따라 분리해서 출력
    for (int i=0; i<M; i++) {
        string p;
        int type;

        cin >> p >> type;
        if (type == 1) {
            cout << member[p] << endl;
        } else {
            for (iter = group[p].begin(); iter != group[p].end(); iter++) {
                cout << * iter << endl;
            }
        }
    }

    return 0;
}