백준 3080번: 아름다운 이름 (Java)

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

3080번: 아름다운 이름

 

 

 

 

 

 

 

 

---

 

풀이

"A, AB, AC, B, C"를 배열하는 경우의 수를 생각해봅시다.

 

이렇게 5개의 이름이 있는 경우, 앞이 "A"로 시작하는 3개의 단어끼리 배열하고, 이후 앞이 "A"로 시작하는 3개의 이름을 하나의 이름을 보아 "A 모음", "B", "C" 3개의 이름을 배열할 수 있습니다. 총 36가지의 경우가 있습니다.

 

 

이를 계산하기 위해 트라이 구조를 이용해보도록 합시다. 트라이에서 첫 번째 단계에 "A", "B", "C" 총 3개의 노드가 있으며, 자식이 있는 "A" 노드는 2개의 자식 노드가 있습니다. 다만, "A"로 시작하면서 바로 끝나는 노드를 세주기 위해, "A"에서 바로 끝난 이름도 추가로 세주면 3개가 됩니다. 이를 위해, 현재 트라이의 자식 노드를 곱하되, 현재 노드에서 끝나는 이름이 있을 경우, 1을 더해주면 됩니다. 코드에서는 isEnd라는 boolean 변수로 체크하고 있습니다.

 

 

 

 

 

 

 

코드

import java.io.*;
 
public class Main {
 
    static final long INF = 1_000_000_007;
    static long[] fact = new long[3001];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        calc(3000);
        TrieNode root = new TrieNode();
        for (int i = 0; i < N; i++) {
            root.insert(br.readLine());
        }
        System.out.println(root.count(root));
    }
 
    static class TrieNode {
        static final int MAX_SIZE = 26;
 
        TrieNode[] childNodes;
        boolean isEnd;
        int cnt;
 
        TrieNode() {
            childNodes = new TrieNode[MAX_SIZE];
        };
 
        void insert(String word) {
            TrieNode cur = this;
            for (int i = 0; i < word.length(); i++) {
                int letter = word.charAt(i) - 'A';
                if (cur.childNodes[letter] == null) {
                    cur.childNodes[letter] = new TrieNode();
                    cur.cnt++;
                }
 
                cur = cur.childNodes[letter];
                if (i == word.length() - 1) {
                    cur.isEnd = true;
                    return;
                }
            }
        }
        
        long count(TrieNode node) {
            if (node.cnt == 0) return 1;
            long ret = (node.isEnd)? fact[node.cnt+1]: fact[node.cnt];
            for (int i = 0; i < 26; i++) {
                if (node.childNodes[i] != null ) {
                    ret *= count(node.childNodes[i]);
                    ret %= INF;
                }
            }
            return ret;
        }
    }
    
    static void calc(int N) {
        fact[0] = 1;
        fact[1] = 1;
        for (int i = 2; i <= N; i++) {
            fact[i] = (fact[i-1] * i) % INF;
        }
    }
}