카테고리 없음
백준 14426, 5052 (Trie)
nownow
2025. 2. 27. 17:28
문자열의 순서를 고려해서 접두사인지 판별할때 활용할 수 있는 Trie
https://www.acmicpc.net/problem/14426
루트 노드를 기준으로 전개해나가고 각 노드에서 여러개의 갈래가 생길 수 있으므로
ArrayList로 노드를 연결시켜준다.
ArrayList대신 HashMap을 사용해도 가능.
import java.io.*;
import java.util.*;
class Main {
static class node {
char ch;
ArrayList<node> nodes = new ArrayList<>();
}
static node root = new node();
static int n, m;
static int result=0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
StringTokenizer token = new StringTokenizer(str);
n = Integer.parseInt(token.nextToken());
m = Integer.parseInt(token.nextToken());
for (int i = 0; i < n; i++) {
str = br.readLine();
add(str);
}
//test();
for(int i=0;i<m;i++){
str=br.readLine();
result+=count(str);
}
System.out.println(result);
}
static int count(String str){
int len = str.length();
node temp = root;
for (int i = 0; i < len; i++) {
char alphabet = str.charAt(i);
boolean newWay = true;
for (node node : temp.nodes) {
if (node.ch == alphabet) { //갈길이 있을경우
temp = node;
newWay = false;
break;
}
}
if(newWay) {
return 0;
}
}
return 1;
}
static void test(){
for(node node : root.nodes){
System.out.println(node.ch);
}
}
static void add(String str) {
int len = str.length();
node temp = root;
for (int i = 0; i < len; i++) {
char alphabet = str.charAt(i);
boolean newWay = true;
for (node node : temp.nodes) {
if (node.ch == alphabet) { //갈길이 있을경우
temp = node;
newWay = false;
break;
}
}
if(newWay) {
node addedNode = new node();
addedNode.ch=alphabet;
temp.nodes.add(addedNode);
temp=addedNode;
}
}
}
}
/*
트라이
루트에서부터 26개의 갈 길을 두고 전개해나감
n개를 그렇게 세팅해두고
m개에서는 갈길이 없으면 멈추고 끝까지 나아가면 결과에 +1
*/https://www.acmicpc.net/problem/5052
예제 입력에서
3
911
97625999
91125426이미 입력된 전화번호의 종료 지점까지 동일한 케이스가 입력될 경우 접미사로 취급된다
해당 케이스만 고려해서 하면
911과 91125426의 순서가 바뀐 케이스를 잡을 수 없다.
한 케이스를 검증할 때, 그 케이스의 마지막 숫자를 확인하는데 이미 입력된 케이스의 Trie를 따라왔다면
그 케이스가 이미 있는 케이스의 접미사라고 취급하여 이 경우도 판별해주어야 한다.
대안
정렬을 통해 길이가 짧은 케이스 먼저 검증을 시도할 수도 있다.
import java.io.*;
import java.util.*;
class Main {
static class node{
char num;
ArrayList<node> arr = new ArrayList<>();
boolean finishLine;
}
static node root = new node();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCase = Integer.parseInt(br.readLine());
for(int i=0;i<testCase;i++){
int numCount = Integer.parseInt(br.readLine());
boolean flag=false;
for(int j=0;j<numCount;j++){
String str = br.readLine();
if(!add(str)){
flag=true;
}
}
if(flag){
System.out.println("NO");
}
else{
System.out.println("YES");
}
root=new node();
}
}
static boolean add(String str){
node temp = root;
int len = str.length();
for(int i=0;i<len;i++){
boolean lastFlag = false;
boolean moveFlag = false;
if(i==len-1) lastFlag=true;
char idxNum = str.charAt(i);
for(node node : temp.arr){
if(node.num==idxNum){ // 같은게 있다면
moveFlag=true;
temp=node;
if(temp.finishLine){
return false;
}
if(i==len-1){
return false;
}
}
}
if(!moveFlag){
node addedNode = new node();
if(lastFlag){
addedNode.finishLine = true;
}
addedNode.num=idxNum;
temp.arr.add(addedNode);
temp=addedNode;
}
}
return true;
}
}
/*
트라이
이미 있는 트라이의 종료지점을 통과해선 안된다. 그럼 아예 STOP
or
내가 마지막인데 이미 있는곳을 왔다
1
3
91125426
911
97625999
*/
//HashMap을 사용하고 정렬처리한 코드
import java.io.*;
import java.util.*;
class Main {
static class node {
char num;
//ArrayList<node> arr = new ArrayList<>();
HashMap<Character, node> arr = new HashMap<>();
boolean finishLine;
}
static node root = new node();
static ArrayList<String> stringArr = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCase = Integer.parseInt(br.readLine());
for (int i = 0; i < testCase; i++) {
int numCount = Integer.parseInt(br.readLine());
boolean flag = false;
for (int j = 0; j < numCount; j++) {
String str = br.readLine();
stringArr.add(str);
}
Collections.sort(stringArr);
for(String tempstr : stringArr){
if (!add(tempstr)) {
flag = true;
}
}
if (flag) {
System.out.println("NO");
} else {
System.out.println("YES");
}
root = new node();
stringArr = new ArrayList<>();
}
}
static boolean add(String str) {
node temp = root;
int len = str.length();
for (int i = 0; i < len; i++) {
boolean lastFlag = false;
boolean moveFlag = false;
if (i == len - 1) lastFlag = true;
char idxNum = str.charAt(i);
//for(node node : temp.arr){
node node = temp.arr.getOrDefault(idxNum,null);
if (node!=null) { // 같은게 있다면
moveFlag = true;
temp = node;
if (temp.finishLine) {
return false;
}
// if (i == len - 1) {
// return false;
// }
}
//}
if (!moveFlag) {
node addedNode = new node();
if (lastFlag) {
addedNode.finishLine = true;
}
addedNode.num = idxNum;
temp.arr.put(idxNum,addedNode);
temp = addedNode;
}
}
return true;
}
}
/*
트라이
이미 있는 트라이의 종료지점을 통과해선 안된다. 그럼 아예 STOP
or
내가 마지막인데 이미 있는곳을 왔다
1
3
91125426
911
97625999
*/
최하단 먼저 작성된 코드
중간 HashMap을 사용하되 정렬하지 않고 if문으로 검사한 코
최상단 아래쪽에 작성되어있는 코드