아름다운 이름

백준 3080번: 아름다운 이름

아이디어

노드 자식 개수만큼 permutation 구하면서 올라가면 된다. 로직 짜는건 쉬운데 그냥 Trie* child[26] 해도 MLE, map<char, Trie*> child해도 MLE.. 그나마 메모리 제일 적게 사용하는 vector 만들고 하나씩 찾으면서 insert한다.

코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = 1e9+7;

struct Trie {
    vector<pair<char, Trie*>> child;
    bool end;

    Trie() {
        end = false;
    }

    ~Trie() {
        for (auto ch : child) {
            delete ch.second;
        }
    }

    void insert(string& s, int idx) {
        if (idx == s.length()) {
            end = true;
            return;
        }
        for (auto ch : child) {
            if (ch.first == s[idx]) {
                ch.second->insert(s, idx+1);
                return;
            }
        }
        pair<char, Trie*> p = {s[idx], new Trie()};
        child.push_back(p);
        p.second->insert(s, idx+1);
    }
};

ll fact(ll n) {
    if (!n) return 1;
    return n*fact(n-1)%MOD;
}

ll solve(Trie* node) {
    ll ret;
    if (node->end) ret = fact(node->child.size()+1);
    else ret = fact(node->child.size());
    for (auto ch : node->child) {
        ret *= solve(ch.second);
        ret %= MOD;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    Trie root;
    int n;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        root.insert(s, 0);
    }
    cout << solve(&root);
    
    return 0;
}

여담

딱뎀 ㄲㅂ
모든 문자를 넣을 필요는 없고 겹치는 부분 제외하고 잘라서 넣으면 메모리 최적화를 할 수 있을 것 같다. 팩토리얼도 미리 계산해두면 좋을듯.