프로그래밍 공방

[백준] 14425번 : 문자열 집합 본문

개발/문제해결

[백준] 14425번 : 문자열 집합

hyosupsong 2021. 2. 2. 01:52

문제

www.acmicpc.net/problem/14425

 

14425번: 문자열 집합

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

www.acmicpc.net

문제해결방법

이 문제는 두 가지 방법으로 풀었다. 

1. Trie / 2. Set

코드1 Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class TrieNode {
    public boolean finish;
    public TrieNode[] next;
    TrieNode() {
        this.finish = false;
        this.next = new TrieNode[26];
    }
}
 
class Trie {
    TrieNode root;
    Trie() {
        root = new TrieNode();
    }
    
    public void add(String s) {
        TrieNode temp = root;
        for(int i=0; i<s.length(); i++) {
            int index = s.charAt(i)-'a';
            if(temp.next[index]==null) temp.next[index] = new TrieNode();
            temp = temp.next[index];
        }
        temp.finish = true;
    }
    
    public boolean isContain(String s) {
        TrieNode temp = root;
        for(int i=0; i<s.length(); i++) {
            int index = s.charAt(i)-'a';
            if(temp.next[index]==null) return false;
            temp = temp.next[index];
        }
        if(temp.finish) return true;
        return false;
    }
}
 
 
public class Main14425_문자열집합 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Trie trie = new Trie();
        for(int i=0; i<N; i++) trie.add(br.readLine());
        for(int i=0; i<M; i++) {
            if(trie.isContain(br.readLine())) answer++;
        }
        System.out.println(answer);
    }
}
cs


코드2 Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main14425_문자열집합 {
 
    public static Set<String> set = new HashSet<String>();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        for(int i=0; i<N; i++) set.add(br.readLine());
        for(int i=0; i<M; i++) {
            if(set.contains(br.readLine())) answer++;
        }
        System.out.println(answer);
    }
}
cs

결과(위가 Set, 아래가 Trie)

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.

'개발 > 문제해결' 카테고리의 다른 글

[백준] 5676번 : 음주 코딩  (0) 2021.02.05
[프로그래머스] 순위 검색  (0) 2021.02.04
[프로그래머스] 외벽 점검  (0) 2021.01.29
[프로그래머스] 광고 삽입  (5) 2021.01.27
[백준] 1238번 : 파티  (0) 2021.01.27
'개발/문제해결' Related Articles more