[BOJ] 14425 문자열 찾기 (Java)

# 출처 : https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

---

트라이 자료구조
O(logN) 또는 O(MlogN)
문자열의 집합을 표현하는 트리 자료구조
문자열을 빠르게 탐색하며 검색을 뜻하는 Retrieval의 중간 음절 Trie를 따왔다고 한다.

장점	단점
빠른 문자열 검색	큰 메모리 용량

시간 초과가 나는 코드지만, 트라이 자료구조를 깨닫게해준 코드라 이를 기반으로 이해하려고 숨겨둔다.

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

public class Main
{
    public static void main(String args[])
    {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            TrieNode trie = new TrieNode();
            for(int i=0; i<n; i++) trie.insert(br.readLine());

            int result = 0;
            for(int i=0; i<m; i++) {
                result += trie.contains(br.readLine()) ? 1 : 0;
            }
            System.out.println(result);
        } catch(Exception e) {
            System.out.println(e);
        }
    }

    static class TrieNode {
        Map<Character, TrieNode> childNode = new HashMap<>();
        boolean terminal;

        TrieNode(){}

        void insert(String s){
            TrieNode trieNode = this;
            for(int i=0; i<s.length(); i++){
                char c = s.charAt(i);

                trieNode.childNode.putIfAbsent(c, new TrieNode());
                trieNode = trieNode.childNode.get(c);
            }
            trieNode.terminal = true;
        }

        boolean contains(String s){
            TrieNode trieNode = this;
            for(int i=0; i<s.length(); i++){
                char c = s.charAt(i);
                TrieNode node = trieNode.childNode.get(c);

                if(node == null) return false;
                trieNode = node;
            }

            return trieNode.terminal;
        }
    }
}

배열을 사용하여 트라이 자료구조를 구현할 수 있다는 부분을 알게되었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main
{
    public static void main(String args[])
    {
        try {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int M = sc.nextInt();

            trieNode tree = new trieNode();
            while(N-- > 0){
                String text = sc.next();
                trieNode now = tree;

                for(int i=0; i<text.length(); i++){
                    char c = text.charAt(i);

                    if(now.next[c - 'a'] == null) now.next[c - 'a'] = new trieNode();
                    now = now.next[c - 'a'];

                    if(i == text.length() - 1) now.isEnd = true;
                }
            }

            int count = 0;
            while(M-- > 0){
                String text = sc.next();
                trieNode now = tree;

                for(int i=0; i<text.length(); i++){
                    char c = text.charAt(i);
                    if(now.next[c - 'a'] == null) break;
                    now = now.next[c - 'a'];
                    if(i == text.length() - 1 && now.isEnd) count++;
                }
            }

            System.out.println(count);
        } catch(Exception e) {
            System.out.println(e);
        }
    }

    static class trieNode {
        trieNode[] next = new trieNode[26];
        boolean isEnd;
    }
}