문제 바로가기

나의 풀이

트라이를 사용하여 문제를 해결하였다. 트라이 노드는 해시맵으로 구성해서 특정 문자(키)가 입력되면 해당하는 자식 노드로 이어지도록 구성하였으며, 해당 노드에는 boolean 변수를 선언하여 마지막인지 아닌지 체크하도록 하였다.

트라이 자료구조는 root 노드는 비어있으며, 간선에 문자나 숫자가 입력되고 다음 자식노드가 마지막이라면 false, 아니라면 true가 들어있는 식이다

엉망으로 그리긴 했으나 이해는 갈 것이다. 각각의 노드 안에 쓴 글자는 실제로 들어있는 것은 아니며, 나의 풀이에서는 true와 false가 실제로 들어있다.

참고로 트라이 자료구조의 시간 복잡도는 문자열 길이와 같으므로 매우 빠르다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

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) {
            Trie trie = new Trie();
            boolean flag = true;

            int n = Integer.parseInt(br.readLine());
            for (int i = 0; i < n; i++) {
                // 일관성이 있는 문자열이라면 true 반환
                // 입력되는 문자열의 앞부분이 존재하거나 혹은 이 문자열이 다른 문자열의 일부분이면 false 반환
                if (!trie.insert(br.readLine())) {
                    flag = false;
                }
            }
            if (flag) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    static class TrieNode {
        // TrieNode의 자식 노드들은 해시맵으로 구성
        Map<Character, TrieNode> childNodes = new HashMap<>();
        // 해당 노드가 마지막이면 true
        boolean isLast;
    }

    static class Trie {

        // root는 하나만 존재
        TrieNode root = new TrieNode();

        boolean insert(String number) {
            TrieNode thisNode = root;
            for (int i = 0; i < number.length(); i++) {
                char c = number.charAt(i);
                // 이 문자가 없으면 새로 만듦
                if (thisNode.childNodes.get(c) == null) {
                    thisNode.childNodes.put(c, new TrieNode());
                }
                // 새로 만들었거나, 존재하는 자식노드로 이동
                thisNode = thisNode.childNodes.get(c);
                // 여기까지 동일했던 문자열이 끝나버린다면 일관성이 없다는 말이므로 false 반환
                if (thisNode.isLast) {
                    return false;
                }
            }
            // 입력받은 문자열 전체 노드를 타고 내려왔는데 자식노드가 존재한다는 말도 일관성이 없다는 말
            if (thisNode.childNodes.size() != 0) {
                return false;
            }
            // 이 문자열은 일관성이 깨지지 않았으므로 마지막 자식노드에 true 넣고 true 반환
            thisNode.isLast = true;
            return true;
        }
    }
}