백준 14426 java : 자료구조, Trie

왜 Trie?

최악의 경우 10000개의 문자열을 10000개의 접두사와 비교해야 하므로 시간초과가 발생한다.

Trie 자료구조?

문자열 검색, 접두어 검색에 특화된 트리 기반 자료구조로,
공통 접두어를 공유하여 저장하는 트리 형태의 자료구조다. -> java에 라이브러리로 구현되어 있지 않으며 직접 구현해야 한다.

참고 :

• https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie
• https://innovation123.tistory.com/116

Trie 자료구조는 왜 사용?

Trie 자료구조는 문자열의 접두어를 탐색하는데 효율이 좋다. 공통의 문자를 일종의 부모 노드로, 자식 노드를 추가해가면서 저장한다.

import java.util.Scanner;
import java.util.*;


public class bj14426 {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEnd;
    }

    static class Trie {
        TrieNode root = new TrieNode();

        void insert(String word) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                node = node.children.computeIfAbsent(ch, c -> new TrieNode());
            }
            node.isEnd = true;
        }

        boolean startsWith(String prefix) {
            TrieNode node = root;
            for (char ch : prefix.toCharArray()) {
                if (!node.children.containsKey(ch)) return false;
                node = node.children.get(ch);
            }
            return true;
        }
    }

    //static Trie 자료구조1 : 문자열 목록 저장
    static Trie trie = new Trie();

    //static 자료구조2 : 접두어 목록 저장
    static List<String> checkList = new ArrayList<>();
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        inputData();
        System.out.println(findAnswer());
    }

    public static void inputData() {
        int N, M;
        int i;

        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine();

        for(i = 0; i < N; i++) {
            String str = sc.nextLine();
            trie.insert(str);  // 문자열 목록 삽입
        }
        for(i = 0; i < M; i++) {
            String prefix = sc.nextLine();
            checkList.add(prefix);  // 접두어 목록 저장
        }
    }

    public static int findAnswer() {
        int answer = 0;

        for(String prefix : checkList) {
            if(trie.startsWith(prefix)) {
                System.out.println(prefix + "는 접두어");
                answer++;
            }
        }

        return answer;
    }
}