[JAVA] 백준 - 14425 : 문자열 집합

문제 링크

14425번: 문자열 집합

 

 

풀이 )

  set을 사용하여 더 빠르게 풀 수 있지만 트라이를 이용해서 풀었다.

  n번의 입력에 대해서 트라이를 생성한 이후

  m번의 입력에 대해서 트라이를 타고가면서 마지막까지 도달한다면 끝인지 확인하여 답을 늘려주었다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");

        int n = Integer.parseInt(in[0]), m = Integer.parseInt(in[1]);
        Node root = new Node();
        while(n-- > 0){
            String str = br.readLine();
            Node cur = root;
            for(int i = 0; i < str.length(); ++i){
                char c = str.charAt(i);
                if(cur.children[c-'a'] == null)
                    cur.children[c-'a'] = new Node();
                cur = cur.children[c-'a'];

                if(i == str.length()-1)
                    cur.isLast = true;
            }
        }

        int ans = 0;
        while(m-- > 0){
            String str = br.readLine();
            Node cur = root;
            for(int i = 0; i < str.length(); ++i){
                char c = str.charAt(i);
                if(cur.children[c-'a'] == null)
                    break;
                cur = cur.children[c-'a'];

                if(i == str.length()-1 && cur.isLast)
                    ans++;
            }
        }
        System.out.println(ans);
    }

    public static class Node{
        Node[] children = new Node[26];
        boolean isLast;

        public Node(){}
    }
}