[BOJ/백준] 6566 - 애너그램 그룹

6566번: 애너그램 그룹

---

---

---

• 제목

애너그램 그룹

---

• 조건

시간 제한 : 1 초

메모리 제한 : 128 MB 

---

• 문제

평생 영어 단어를 암기한 준민이는 단어를 애너그램 그룹으로 나누려고 한다.

단어 w가 단어 v의 애너그램이 되려면, 단어 w의 알파벳 순서를 바꿔서 v를 만들 수 있어야 한다. 이렇게 애너그램인 단어들을 묶어서 애너그램 그룹이라고 한다. 그룹의 크기는 그 그룹에 포함된 단어의 수이다.

단어가 주어졌을 때, 크기가 가장 큰 애너그램 그룹 다섯 개를 구하는 프로그램을 작성하시오.

---

• 입력

입력은 최대 30,000 줄로 이루어져 있고, 각 줄에는 알파벳 소문자로 이루어진 단어가 하나씩 주어진다. 입력은 EOF로 끝난다. 

---

• 출력

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

각 그룹을 출력할 때, 크기와 포함된 단어를 출력하며, 단어는 사전 순으로 출력해야 한다. 같은 단어는 한 번만 출력한다.

---

예제 입력1	예제 출력1
undisplayed trace tea singleton eta eat displayed crate cater carte caret beta beat bate ate abet	Group of size 5: caret carte cater crate trace . Group of size 4: abet bate beat beta . Group of size 4: ate eat eta tea . Group of size 1: displayed . Group of size 1: singleton .

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
using namespace std;
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'
map<string, priority_queue<string, vector<string>, greater<string>>> dict;
struct compare{
    bool operator()(pair<int, string> a, pair<int, string> b){
        if(a.first == b.first) return dict[a.second].top() > dict[b.second].top();
        return a.first < b.first;
    }
};
int main() {
    fastio;
    string word, sorted;
    while(cin >> word){
        sorted = word;
        sort(sorted.begin(), sorted.end());
        if(dict.find(sorted) != dict.end()){
            dict[sorted].push(word);
        }
        else{
            priority_queue<string, vector<string>, greater<string>> tmp;
            dict.insert({sorted, tmp});
            dict[sorted].push(word);
        }
    }
    priority_queue<pair<int, string>, vector<pair<int, string>>, compare> que;
    // size, sorted, front word
    for(auto iter = dict.begin() ; iter != dict.end() ; iter++){
        que.push({iter->second.size(), iter->first});
    }
    int sz = que.size();
    if(sz > 5) sz = 5;
    while(sz--){
        string curr = que.top().second, prev = "#";
        que.pop();
        cout << "Group of size " << dict[curr].size() << ": ";
        while(!dict[curr].empty()){
            if(prev != dict[curr].top()) cout << dict[curr].top() << ' ';
            prev = dict[curr].top();
            dict[curr].pop();
        }
        cout << "." << endl;
    }
    return 0;
}