백준 3080번 : 아름다운 이름 - 트라이 , Java

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

3080번: 아름다운 이름

 

1.문제설명

입력받는 이름들로 트라이 구조를 만들고

분기점과 문자열이 끝나는 점을 바탕으로

순열 계산을 하면 학생들을 배치할 수 있는 경우의 수를 구해낼 수 있다.

 

 

2.문제풀이코드 C++

//package org.example;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    final int MX = 26;
    final long mod = 1000000007;
 
    public long factorial(int n) {
        long ret = 1;
        for (int i = 1; i <= n; i++) {
            ret *= i;
            ret %= mod;
        }
        return ret;
    }
 
    class Trie {
        Trie[] child;
        int childNum;
        int end;
 
        public Trie() {
            child = new Trie[MX];
            Arrays.fill(child, null);
            childNum = end = 0;
        }
 
        public void insert(String str) {
            Trie cur = this;
            for (int i = 0; i < str.length(); i++) {
                int ch = str.charAt(i) - 'A';
                if (cur.child[ch] == null) {
                    cur.child[ch] = new Trie();
                    cur.childNum++;
                }
                cur = cur.child[ch];
            }
            cur.end = 1;
        }
 
        public long getAns() {
            long ret = factorial(this.childNum + this.end);
            for (Trie nx : this.child) {
                if(nx==null) continue;
                ret *= nx.getAns();
                ret %= mod;
            }
            return ret % mod;
        }
    }
 
 
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(br.readLine());
 
        Trie root = new Trie();
 
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            root.insert(str);
        }
 
        System.out.println(root.getAns());
    }
 
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}