BOJ#5670 휴대폰 자판

BOJ#5670 휴대폰 자판

* 문제

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

* 풀이

카카오 블라인드 채용 - 3차 코딩테스트 5번 문제와 유사합니다.

Trie를 사용하여 풀어보았습니다. 

1. 모든 문자열을 Trie에 저장한 후

2. child의 개수가 2 이상인 경우, terminal 노드인데 child가 존재하는 경우를 카운트하였습니다.

부족한 점이 있으면 댓글로 알려주세요. 감사합니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/a3f55a12084c8b798e96dd86eedbdc8661595777/BOJ%235670/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static final int SIZE = 26;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line;
        while ((line = br.readLine()) != null) {

            Trie trie = new Trie();

            int N = Integer.parseInt(line);

            String[] str = new String[N];

            for (int i = 0; i < N; i++) {

                str[i] = br.readLine();
                trie.insert(str[i]);
            }

            for (int i = 0; i < SIZE; i++) {

                if (trie.root.children[i] != null) {

                    trie.check(trie.root.children[i], 1);
                }
            }

            System.out.printf("%.2f", (double) cnt / N);
            System.out.println();

            cnt = 0;
        }


    }
}

class Trie {

    TrieNode root;

    Trie() {

        root = new TrieNode();
    }

    private int toNumber(char c) {

        return c - 'a';
    }

    void insert(String key) {

        int length = key.length();
        TrieNode currentNode = root;

        for (int i = 0; i < length; i++) {

            int next = toNumber(key.charAt(i));

            if (currentNode.children[next] == null) {

                currentNode.children[next] = new TrieNode();
                currentNode.nChild++;
            }


            currentNode = currentNode.children[next];
        }

        currentNode.isTerminal = true;
    }

    void check(TrieNode node, int ret) {

        if (node.isTerminal) {

            Main.cnt += ret;
        }

        if (node.nChild >= 2) {

            ret++;
        }

        if (node.isTerminal && node.nChild == 1) {

            ret++;
        }

        for (int i = 0; i < Main.SIZE; i++) {

            if (node.children[i] != null) {

                check(node.children[i], ret);
            }
        }

    }
}

class TrieNode {

    TrieNode[] children = new TrieNode[Main.SIZE];
    boolean isTerminal;

    int nChild = 0;

    TrieNode() {

        isTerminal = false;

        for (int i = 0; i < Main.SIZE; i++) {

            children[i] = null;
        }
    }
}