반응형
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(){}
}
}
반응형
'문제풀이 > 백준' 카테고리의 다른 글
[JAVA] 백준 - 10816 : 숫자카드2 (0) | 2021.02.16 |
---|---|
[JAVA] 백준 - 2116 : 주사위 쌓기 (0) | 2021.02.15 |
[JAVA] 백준 - 13549 : 숨바꼭질3 (0) | 2021.02.13 |
[JAVA] 백준 - 5052 : 전화번호 목록 (0) | 2021.02.13 |
[C++] 백준 - 1744 : 수 묶기 (0) | 2021.01.26 |