ALGORITHM/BOJ
[백준] 14425 문자열 집합
0298
2021. 2. 2. 22:57
14425번: 문자열 집합
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어
www.acmicpc.net
2021-02-02
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
61
62
63
64
65
66
67
68
69
|
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);
}
}
|
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
|
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);
}
}
|
cs |
#문제풀이
Trie 자료구조를 공부하기 위해서 여러 블로그들을 검색해서 풀어봤다.
+) 찾아보니 Trie가 아니라 set이나 map으로 푼 사람들도 있길래 set으로도 한 번 제출해봤다.
아래 trie로 푼 것보다 set으로 푼게 훨씬 빠른 것을 볼 수도 있다.
