[백준] 14425 문자열 집합

www.acmicpc.net/problem/14425

14425번: 문자열 집합

2021-02-02

---

1. Trie

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class TrieNode {
    public TrieNode next[]; // 다음 (자식) 노드
    public boolean isLast; // 문자열이 끝난지를 체크한다.
    
    TrieNode() {
        next = new TrieNode[26]; // 알파벳
        this.isLast = false; 
    }
}
 
class Trie {
    TrieNode root;
    Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++) {
            int ch = word.charAt(i) - 'a';
            if(node.next[ch] == null) node.next[ch] = new TrieNode();
            node = node.next[ch];
        }
        node.isLast = true;
    }
    
    public boolean contains(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++) {
            int ch = word.charAt(i) - 'a';
            if(node.next[ch] == null) return false;
            node = node.next[ch];
        }
        if(node.isLast) return true;
        return false;
    }
    
}
 
public class Main14425 {
    public static int N, M, answer;
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        answer = 0;
        
        Trie t = new Trie();
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine().trim());
            String str = st.nextToken();
            if(!t.contains(str)) t.insert(str);
        }
        
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine().trim());
            String str = st.nextToken();
            if(t.contains(str)) answer++;
        }
        
        System.out.println(answer);
    }
}
 

2. Set

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main14425_2 {
    public static int N, M, answer;
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        answer = 0;
        Set<String> set = new HashSet<>();
        for(int i = 0; i < N; i++) {
            set.add(new StringTokenizer(bf.readLine().trim()).nextToken());
        }
        for(int i = 0; i < M; i++) {
            if(set.contains(new StringTokenizer(bf.readLine().trim()).nextToken())) answer++;
        }        
        System.out.println(answer);
    }
}
 

 

#문제풀이

Trie 자료구조를 공부하기 위해서 여러 블로그들을 검색해서 풀어봤다. 

 

+) 찾아보니 Trie가 아니라 set이나 map으로 푼 사람들도 있길래 set으로도 한 번 제출해봤다.

아래 trie로 푼 것보다 set으로 푼게 훨씬 빠른 것을 볼 수도 있다.