[C++][백준 6566] 애너그램 그룹

문제

접근 방법

애너그램 그룹에 속한 모든 단어는 정렬을 했을 때 동일한 결과가 나옵니다.
그렇기에 정렬된 값을 키로 활용하면 애너그램 그룹을 나눌 수 있습니다.

이후 출력에 적혀있는 사항을 준수하여 출력하면 됩니다.

코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
using namespace std;
string word;
map<string, pair<string, vector<string>>> m;
set<string> isVisited;
vector<pair<string, vector<string>>> v;

const bool compare(const pair<string, vector<string>> &a, const pair<string, vector<string>> &b)
{
    if (a.second.size() == b.second.size())
    {
        return a.second[0] < b.second[0];
    }

    return a.second.size() > b.second.size();
}

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);

    while (cin >> word)
    {
        string w = word;

        sort(word.begin(), word.end());

        if (m[word].first == "")
        {
            m[word].first = w;
        }
        else
        {
            m[word].first = min(m[word].first, w);
        }

        m[word].second.push_back(w);
    }
}

void solve()
{
    v.reserve(m.size());

    for (auto &p : m)
    {
        sort(p.second.second.begin(), p.second.second.end());
        v.push_back({p.first, p.second.second});
    }

    sort(v.begin(), v.end(), compare);

    for (int i = 0; i < min(5, static_cast<int>(v.size())); ++i)
    {
        const auto &p = v[i];

        cout << "Group of size " << p.second.size() << ": ";

        for (const auto &s : p.second)
        {
            if (isVisited.find(s) != isVisited.end())
            {
                continue;
            }

            isVisited.insert(s);
            cout << s << " ";
        }
        cout << ".\n";
    }
}

int main()
{
    input();
    solve();
    return 0;
}

풀이

출력에서 준수해야 하는 사항은 아래와 같습니다.

• 크기가 가장 큰 애너그램 다섯 개를 출력한다. 만약, 그룹의 수가 다섯개보다 작다면, 모두 출력한다.
• 그룹은 크기가 감소하는 순으로, 크기가 같을 때는 각 그룹에서 가장 사전 순으로 앞서는 단어의 사전 순
• 단어는 사전 순으로 출력해야 한다. 같은 단어는 한 번만 출력한다.

정렬을 할 때 기준은 각 그룹에서 가장 사전 순으로 앞서는 단어이기에 가장 사전 순으로 앞서는 단어를 알고 있어야 합니다.

또한 같은 단어는 한 번만 출력된다는 것은 동일한 단어의 개수는 세어주지만 실제 출력에서는 1개만 출력된다는 것입니다. 예를 들어 a가 3번 들어갔다면 개수는 3개를 세어주는데 출력에선 a가 1번만 나오는 것입니다.