[JAVA] Trie 알고리즘

java 트라이 알고리즘, Trie 알고리즘 등등으로 검색해서 오신 분들은 귀찮더라도 개념 자체는 다른 분들이 친절하게

그림까지 다 그려가면서 설명을 잘 해놓았기 때문에 다른 분들 글과 그림을 보면서 설명을 듣고 오시길 바랍니다!

 

사실 저도 엄청 검색을 해보고 많은 글을 보고 했었는데 먼가 진짜 쉽게 짜놓은 트라이 알고리즘은 없어서

이 새벽에 미친 듯이 고민해가며 트라이를 짜왔습니다.

 

문제는 SW Expert에 문자열 교집합이라는 문제를 참고로 하였고

사실 이 문제는 트라이로 풀면 메모리가 오버되어 절대로 풀 수가 없습니다. ㅎ....

이거 때문에 왜 런타임 에러일까 하면서 한참을 고민했네요

 

B형을 준비하시는 분들은 LinkedList를 구현하는 것을 먼저 보고 오시길 추천드리며

LinkedList를 아신다면 보셔도 무관하실 것 같습니다.

일단 위에 다른 분이 쓴 글을 보면서 개념을 익히고 오라고 하였지만 간단하게 설명하면

문자열 혹은 숫자를 하나씩 쪼개서 각각을 객체안의 배열에 넣고 다음 문자( 혹은 숫자 ) 를 다시

다음 객체의 배열에 넣는 것 입니다.

 

LinkedList에서도 객체 안에 Next를 만들어 넣어서 다음 값이 객체안의 Next가 되도록 하여 구현하는데

 

트라이도 사실상 비슷합니다.

 

차이점 이라면 LinkedList는 현재 값이 있고 다음 값이 없으면 Next가 null 인 반면

트라이는 자식이 무조건 존재 하고 다음 값이 없으면 자식의 자식이 없는 형태 입니다.

 

클래스는 다음과 같이 짰습니다.

 

static class TrieNode{
	TrieNode[] child;
	boolean isTerminal;
	public TrieNode() {
		this.child = new TrieNode[26];
		this.isTerminal = false;
	}
}

 

이름도 child라고 표시하였고

boolean의 경우 특정 문자열이 여기서 끝이 났나요? 하고 체크를 하였습니다.

 

예를 들면 

abcd와 abc 가 있을 경우

c에서 boolean이 true, d에서 boolean true가 됩니다.

 

배열의 크기가 26인 경우 이 문제에서는 알파벳을 하기에 26개를 썼습니다.

 

nRoot = new TrieNode();
node = nRoot;
for(int i=0; i<n; ++i) {
	node = nRoot;
	s = nArr[i];
	for(int j=0; j<s.length(); ++j) {
		c = s.charAt(j);
		if(node.child[c - 'a'] == null) {
			node.child[c - 'a'] = new TrieNode();
		}
		if(j == s.length()-1) {
			node.isTerminal = true;
		}else {						
			node = node.child[c-'a'];
		}
	}
}

 

처음에 n개를 먼저 입력받게 되는데

이때 DB라고 표현해야할까 먼저 저장할 곳을 nRoot라고 선언하였고 node의 경우 중간에 활용하기 위해 선언하였습니다.

사실 새벽에 해서 멘탈 터져서 저렇게 작성하였으니 더 좋은 방법이 있다면 알아서 하시거나 댓글 부탁드려요 ㅠ

 

1. n개의 문자열을 확인합니다.

2. 각 문자열의 길이만큼 for문을 돌게 되는데 

   이 때 node의 child의 인덱스가 null일 경우 아직 만들어 지지 않았기에 new 를 하여 만들어 줍니다.

( 길만 만들어주면 있다고 생각 되기에 따로 표시할 필요가 없어요! null이면 그 문자열은 없다! )

 

3. 문자열의 끝이라면 끝이라고 Terminal을 표시 / 아니라면 다음 문자열로 가도록 해주시면 됩니다.

 

( 참고, node = node.child[c= 'a'] 라고 적어주면서 자꾸 덮었지만 while( true ) 등을 활용해서 작성하셔도 무관합니다. )

다시 읽어보니 이게 무슨 말인지 저도 모르겠네요;;

 

for(int i=0; i<m; ++i) {
	node = nRoot;
	s = mArr[i];
	for(int j=0; j<s.length(); ++j) {
		c = s.charAt(j);
		if(node.child[c-'a'] == null) {
			break;
		}
		if(j == s.length()-1) {
			if(node.isTerminal) {
				result++;
			}
		}else {
			node = node.child[c-'a'];
		}
	}
}

 

다시 비교를 위해 m개를 입력 받을때는 root 부터 따라 내려와 비교하는 문자열이 끝이 났는데 여기서 끝나는 문자가 있니? boolean을 확인해주시면 아 나도 여기서 끝났는데 먼저 받은 입력에서도 끝이나는 문자가 있구나 하고 확인이 가능해 중복되는 문자가 하나 있다 라고 표시 해주시면 됩니다.

 

그리고 맨 처음 if문은 아예 통로조차 만들어져 있지 않으면 무조건 중복되지 않는 문자열이기에 바로 break를 걸어주었습니다.

 

전체 코드는 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution2948 {
	static class TrieNode{
		TrieNode[] child;
		boolean isTerminal;
		public TrieNode() {
			this.child = new TrieNode[26];
			this.isTerminal = false;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		String[] str = null;
		int n = 0;
		int m = 0;
		String[] nArr = null;
		String[] mArr = null;
		TrieNode nRoot = null;
		String s = "";
		char c = '0';
		int result = 0;
		TrieNode node = null;
		for(int t=1; t<=T; ++t) {
			str = br.readLine().split(" ");
			n = Integer.parseInt(str[0]);
			m = Integer.parseInt(str[1]);
			nArr = br.readLine().split(" ");
			mArr = br.readLine().split(" ");
			result = 0;
			nRoot = new TrieNode();
			node = nRoot;
			for(int i=0; i<n; ++i) {
				node = nRoot;
				s = nArr[i];
				for(int j=0; j<s.length(); ++j) {
					c = s.charAt(j);
					if(node.child[c - 'a'] == null) {
						node.child[c - 'a'] = new TrieNode();
					}
					if(j == s.length()-1) {
						node.isTerminal = true;
					}else {						
						node = node.child[c-'a'];
					}
					
				}
			}
			for(int i=0; i<m; ++i) {
				node = nRoot;
				s = mArr[i];
				for(int j=0; j<s.length(); ++j) {
					c = s.charAt(j);
					if(node.child[c-'a'] == null) {
						break;
					}
					if(j == s.length()-1) {
						if(node.isTerminal) {
							result++;
						}
					}else {
						node = node.child[c-'a'];
					}
				}
			}
			bw.write("#"+t+" "+result+"\n");
		}
		bw.close();
		br.close();

	}

}

 

 

혹시 문의 사항 있으면 댓글을 남겨주세요

 

성심성의 껏 작성한 글을 읽어주셔서 감사합니다.

 

추천 문제로는 백준(BOJ)에 전화번호 목록이라는 문제가 있습니다.