Trie 자료구조 - 14425

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

 

문제
총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

 

입력
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

 

출력
첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

 

Trie 자료구조

DAVID, MARIA, MARIO라는 문자를 입력 받으면 아래의 그림과 같이 저장된다.
마지막 줄에 작성되어 있는 D, A, O에 도달하면 Terminal 노드는 True, 도달하지 못한 경우 false이다.
예를 들어 DAVI라는 값이 대입 된다면 마지막 D, A, O 노드에 도달하지 못하였기 때문에 false로 판단한다. 즉, 동일하지 않은 문자열 이라고 판단할 수 있는 것이다.

[출처] https://www.interviewcake.com/concept/java/trie

Tire Node 구현 코드

public class TrieNode {

        Map<Character, TrieNode> childNode = new HashMap<>();
        boolean terminal; // 동일 여부 판단 Default false

        TrieNode() {
            //기본 생성자
        }
		
        // Trie Node 생성
        public void insert(String word) {
            TrieNode trieNode = this;
            for(int i = 0;  i < word.length(); i++) {
                char c = word.charAt(i);

                //childNode에 c가 없으면 추가해 준다.
                trieNode.childNode.putIfAbsent(c, new TrieNode());
                trieNode = trieNode.childNode.get(c);

				//마지막 노드라면 Terminal을 True로 설정해 준다.
                if(i == word.length()-1) {
                    trieNode.terminal = true;
                    return;
                }
            }
        }
        
        // 포함 여부 판단
        public boolean contains(String word) {
            TrieNode trieNode = this;
            for(int i = 0; i < word.length(); i++) {
                char c = word.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.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class No_14425  {
    private static class TrieNode {

        Map<Character, TrieNode> childNode = new HashMap<>();
        boolean terminal;
        
        private void insert(String word) {
            TrieNode trieNode = this;
            for(int i = 0;  i < word.length(); i++) {
                char c = word.charAt(i);

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

                if(i == word.length()-1) {
                    trieNode.terminal = true;
                    return;
                }
            }
        }

        private boolean contains(String word) {
            TrieNode trieNode = this;
            for(int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                TrieNode node = trieNode.childNode.get(c);
                if(node == null) return false; 
                trieNode = node;
            }
            return trieNode.terminal;
        }

    }

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        TrieNode trieNode = new TrieNode();
        // 각각의 문자열을 Trie 자료구조로 변환
        for(int i = 0; i < N; i++) trieNode.insert(bufferedReader.readLine());

        int count = 0;
        for(int i = 0; i < M; i++) {
        	//참을 반환하면 집합이므로 횟수 증가
            if (trieNode.contains(bufferedReader.readLine())) count++;
        }

        System.out.print(count);
    }
}