반응형

문제 링크

 

14425번: 문자열 집합

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.  다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어

www.acmicpc.net

 

 

풀이 )

  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(){}
    }
}
반응형

+ Recent posts