BOJ#5052 전화번호 목록

BOJ#5052 전화번호 목록

* 문제

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

* 풀이

저는 이 문제를 Trie를 이용해서 풀어보았습니다.

Trie를 처음 공부하고 풀어보는 것이라서 부족한점이 있을 것 같습니다. 댓글로 알려주시면 감사하겠습니다.

,

1. 일단 전화번호 목록을 배열에 저장한 후 정렬을 진행합니다.

2. Trie 자료구조에 Insert합니다.

3. 이 과정에서 terminal 노드인데 children이 추가되는 경우 '일관성 있지 않은' 목록으로 판단합니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%235052/src/Main.java

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

public class Main {

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

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

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {

            int n = Integer.parseInt(br.readLine());
            String[] num = new String[n];

            Trie trie = new Trie();
            boolean ret = true;

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

                num[i] = br.readLine();
            }

            Arrays.sort(num);

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

                if (!trie.insert(num[i])) {

                    ret = false;
                    break;
                }
            }

            System.out.println(ret ? "YES" : "NO");
        } // ~ test case loop
    }
}

class Trie {

    private TrieNode root;

    Trie() {

        root = new TrieNode();
    }

    private int toNumber(char c) {

        return c - '0';
    }

    boolean insert(String key) {

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

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

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

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

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

            currentNode = currentNode.children[next];

            if (currentNode.isTerminal && i + 1 < length) {

                return false;
            }
        }

        currentNode.isTerminal = true;

        return true;
    }
}

class TrieNode {

    TrieNode[] children = new TrieNode[10];
    boolean isTerminal;

    TrieNode() {

        isTerminal = false;

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

            children[i] = null;
        }
    }
}