[Algorithm] 트라이(trie) / 백준 14425번 문자열 집합

[Algorithm] 트라이(trie)

트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조이다.

트라이의 핵심 이론

트라이는 일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행한다.
트리의 루트에서부터 자식을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다.
트라이 자료구조의 특징은 다음과 같다.

N진 트리 : 문자 종류의 개수에 따라 N이 결정된다. 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성된다.
루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지한다.

다음은 영단어, apple, air, apply를 순서대로 트라이 자료구조에 삽입하는 모습이다.

루트 노드는 공백을 유지한다.
apple의 각 알파벳ㅅ에 해당하는 노드를 생성한다.
그 다음으로 air을 삽입할 때는 루트 노드에서부터 검색한다. a 노드는 공백 상태가 아니므로 이동하고, i와 r은 공백 상태이므로 신규 노드를 생성한다.
apply를 삽입할때도 검색 노드가 공백 상태이면 신규 노드를 생성하고, 아니면 이동하는 원리로 트라이 자료구조를 구현한다.

백준 p14425 - 문자열 집합

이 문제는 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇개인지 구하는 문제이다.

사실 전에도 한번 풀었던 문제인데, 그때는 해시맵을 이용해 풀었다.
<String,Integer> 형태인 Hashmap을 만들었고 키에는 문제에서 주어지는 문자열을, 그리고 값은 필요 없기 때문에 0을 넣어주었다.
그 다음으로 M개의 테스트할 문자열들을 하나씩 입력 받는다. 입력 받을때 constrainsKey 함수를 이용해여 미리 만들어둔 map에 그 문자열이 있으면 count 변수의 값을 1씩 증가시킨다.
그리고 마지막으로 이 count 값을 출력해주었다.

  
import java.io.*;
import java.util.*;
public class Main {
	static int N;
	static int M;
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		Map<String,Integer> map = new HashMap<>();
		for(int i=0;i<N;i++) {
			map.put(br.readLine(),0);
		}
		int count =0;
		for(int i=0;i<M;i++) {
			String str = br.readLine();
			if(map.containsKey(str)) count++;
		}
		System.out.println(count);
		
		
	}
}

사실 트라이 보다는 해시맵을 이용해 푸는 것이 더 간단하고 빠른 문제이지만, 트라이 연습을 위해 트라이로 문제를 다시 풀어보았다.
문제를 트라이를 이용해 풀려고 한다면, 집합 S에 속해 있는 단어들을 이용해 트라이 자료 구조를 생성하고, 트라이 검색을 이용해 문자열 M애의 포함 여부를 카운트 하는 식으로 풀면 된다..

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

public class p14425 {
    //백준 14425 문자열 집합
    static int N;
    static int M;
    public static void main(String[]args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Node root = new Node();
        while(N>0){
            String text = br.readLine();
            Node now = root;
            for(int i=0;i<text.length();i++){
                char c = text.charAt(i);
                if(now.next[c-'a'] == null)
                    now.next[c-'a'] = new Node();
                now = now.next[c-'a'];
                if(i==text.length()-1)
                    now.isEnd = true;
            }
            N--;
        }
        int count =0;
        while(M>0){
            String txt = br.readLine();
            Node now = root;
            for(int i=0;i<txt.length();i++){
                char c = txt.charAt(i);
                if(now.next[c-'a']==null) break;
                now = now.next[c-'a'];
                if(i == txt.length()-1 && now.isEnd) count++;
            }
            M--;

        }
        System.out.println(count);

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

}

[Algorithm] 트라이(trie) / 백준 14425번 문자열 집합