[BOJ 12865] 아름다운 이름(c++)

https://www.acmicpc.net/problem/12865

문제 개요

n개의 이름이 입력되고, 이름의 순서의 가짓수(순열)를 계산해야 한다. 같은 알파벳 순서로 시작하는 두 이름의 사이에는 모두 그 순서로 시작하는 단어가 있어야 한다. 예를 들어, 두 이름이 MARTHA와 MARY는 모두 MAR로 시작한다.  따라서, 두 단어 사이에는 MARCO나 MARVIN과 같이 MAR로 시작하는 이름만이 존재할 수 있다. (MAY는 그 사이에 있을 수 없다)

(3 <= n <= 3,000)

(이름의 길이 <= 3000)

 

풀이

트라이의 경로 공유 특성을 활용해 같은 경로의 이름들을 구분하였다. 한 노드에서 여러 자식들이 연결된다면 (자식 노드 수)!을 계산해 계속 곱해주면, 모든 경우의 수를 구할 수 있다. 현재 노드에서 하위노드의 수로만 순서를 정하면 된다. 그리고 재귀적인 방식으로 하위 노드들로 파고 들며 그 값을 계속 계산해주어야 한다. 같은 알파벳 순서를 공유하는 이름끼리는 붙어있어야 하기 때문이다.  또한, 하위 노드의 수가 1이라면 여기서는 경우의 수가 1이기 때문에 탐색하지 않아도 된다. 트라이의 메타 데이터로 자식 경로의 수와 경로 별 자식들의 수를 저장하면 이를 구현할 수 있다. 

 

구현한 후 제출했더니, 메모리 초과가 났다. 그도 그럴것이 이름의 길이가 최대 3000이고, 한 노드당 328Byte이므로 무턱대고 트라이를 구현하면 메모리초과가 날 수 밖에 없었다. 그래서 정렬해준 뒤 i + 1 요소와 비교하여 문자열이 달라지는 순간 끊어지는 로직을 추가하였더니, 통과되었다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

const long long mx = 1e9 + 7;

int n;
struct node {
    int n;
    int cnt[27];
    node* child[27];
};

node* root;
node pool[1000000];
int p_cnt;
long long dp[3001];
long long res;

node* new_node() {
    for (int i = 0; i < 27; i++) {
        pool[p_cnt].child[i] = nullptr;
    }
    return &pool[p_cnt++];
}

void insert(string str, string cmp) {
    node* cur = root;
    bool flag = true;
    for (int i = 0; i < str.size(); i++) {
        int x = str[i] - 'A';
        if (!cur->cnt[x]) {
           
            cur->n++;
        }
        cur->cnt[x]++;
        if (!cur->child[x]) {
            cur->child[x] = new_node();
        }
        if (cur->cnt[x] == 1 && str[i] != cmp[i]) {
            flag = false;
            break;
        }
        cur = cur->child[x];

    }
    if (flag) {
        if (!cur->cnt[26]) {
            cur->n++;
        }
        cur->cnt[26]++;
    }
}

long long calc(int k) {
    if (dp[k]) return dp[k];
    if (k <= 1) return 1;
    return dp[k] = (k * calc(k - 1)) % mx;
}

void search(node x) {
    res = (res * calc(x.n)) % mx;
    for (int i = 0; i < 26; i++) {
        if (x.cnt[i] > 1) {

            search(*x.child[i]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    root = new_node();
    string str_arr[3001];
    for (int i = 0; i < n; i++) {
        cin >> str_arr[i];
    }
    sort(str_arr, str_arr + n);
    for (int i = 0; i < n - 1; i++) {
        insert(str_arr[i], str_arr[i + 1]);
    }
    insert(str_arr[n - 1], str_arr[n - 1]);
    res = 1;
    search(*root);
    cout << res << '\n';
    return 0;
}