Algorithm, Trie
Trie(트라이)
- 문자열에서의 검색을 빠르게 해주는 자료구조
- 정수형 자료형에 대해 이진검색트리를 이용하면 O(logN)의 시간만에 검색가능하다
- 하지만 최대 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 된다
- 이를 개선 한것이 트라이 !! O(M)
구현
- Trie.java
package org.study;
import java.util.*;
public class Trie {
private TrieNode root;
// -- 생성자 , 루트노드 생성
public Trie() {
root = new TrieNode(' ');
}
// -- 삽입
public void insert(String word) {
// 삽입하려는 문자가 모두 존재할때
if(search(word) == true) return;
TrieNode current = root;
for (char ch : word.toCharArray()) {
TrieNode child = current.subNode(ch);
if(child != null) {
current = child;
}
else {
// ch 문자가 있으면 그 노드 리턴
current.childList.add(new TrieNode(ch));
current = current.subNode(ch);
}
current.count++;
}
current.terminal = true;
}
// -- 검색
public boolean search(String word) {
TrieNode current = root;
// 문자열을 문자배열로 쪼개서 비교
for(char ch : word.toCharArray()) {
// 해당 문자의 노드가 없으면 false
if(current.subNode(ch) == null)
return false;
// 해당 문자가 존재하면, 현재 노드에 서브 노드 저장해서 단계별로 내려감
else
current = current.subNode(ch);
}
// a,p,p,l,e 가 있을때,
// word = apple 이면 true / word = appleb 이면 false
if(current.terminal == true) return true;
return false;
}
// -- Trie에 저장된 단어 목록 Iterator타입으로 반환
public Iterator<String> iterator(){
Set<String> elementsInTrie = new TreeSet<>();
// 저장됨 데이터를 elementsIntrie에 저장
recursiveCallPrint(root, "", elementsInTrie);
Iterator<String> elementsInTrieSet = elementsInTrie.iterator();
return elementsInTrieSet;
}
private void recursiveCallPrint(TrieNode currNode,
String key, Set<String> elementsInTrie) {
if(currNode.terminal) {
elementsInTrie.add(key);
}
LinkedList<TrieNode> children = currNode.childList;
Iterator<TrieNode> childIter = children.iterator();
String sKey = key;
while (childIter.hasNext()) {
TrieNode nextNode = childIter.next();
// 문자열 합치기 (키+문자)
String s = sKey + nextNode.nodeChar;
// 재귀 호출 (다음 노드, 키값, 저장셋)
recursiveCallPrint(nextNode, s, elementsInTrie);
}
}
public void printWord() {
System.out.println("▶Elements in the TRIE are :");
Iterator<String> itr = iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
System.out.println("===================");
}
}
/*
* 트라이 노드 정의
* */
class TrieNode implements Comparable<TrieNode>{
char nodeChar; // 문자저장
boolean terminal; // 리프 노드 여부
int count; // 해당 노드 사용수, 내 노드에 몇개의 가지가 있는지
LinkedList<TrieNode> childList; // 자식 노드 리스트
// constructor
public TrieNode(char c) {
childList = new LinkedList<>();
terminal = false;
nodeChar = c;
count = 0;
}
boolean getTerminal() {
return terminal;
}
// 해당 노드가 가지고 있는 자식 노드들중에서 입력받은 문자가 있으면 그 노드 리턴
public TrieNode subNode(char nextChar) {
// 자식 노드들이 있다면
if(childList != null) {
for(TrieNode eachChild:childList) {
if(eachChild.nodeChar == nextChar) {
return eachChild;
}
}
}
return null;
}
@Override
public int compareTo(TrieNode other) {
return Character.compare(this.nodeChar, other.nodeChar);
}
@Override
public String toString() {
return this.nodeChar+"("+this.terminal+") ";
}
}
- TrieTest.java
package org.study;
public class TrieTest {
public static void main(String[] args) {
//자료구조에 저장할 데이터
// String data[] = {"abcd","abcf", "bcd","a", "bcdefg", "defg", "aac", "baz", "foo", "foobar","자바"};
Trie matcher = new Trie();
matcher.insert("abcd");
matcher.insert("abcf");
matcher.insert("bcd");
//trie에 있는 데이터 콘솔에 나열.
matcher.printWord();
System.out.println(matcher.search("abc"));
}
}
- 문제풀이
package org.study;
//https://code0xff.tistory.com/76
//https://kim6394.tistory.com/175
//https://m.blog.naver.com/javaking75/140211950640
import java.io.*;
public class TrieTest_boj5052 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int i;
private static String str;
private static int res;
static int nextInt() {
try {
i = Integer.parseInt(br.readLine().trim());
}catch (Exception e) {}
return i;
}
static String nextLine() {
try {
str = br.readLine().trim();
}catch (Exception e) {}
return str;
}
public static void main(String[] args) {
int T = nextInt(); // testcase
while(T>0) {
T--;
int N = nextInt(); // 전화번호 수
Node root = new Node('r',0);
for(int n=1; n<=N; n++) {
Node node = root;
String str = nextLine(); // 전화번호 한줄읽음
for (int i=0; i<str.length(); i++) {
char c = str.charAt(i);
// 해당 글자로 시작하는 가지가 없으면
// 해당 글자로 시작하는 가지를 만들어준다
// c-'0' : char to int
System.out.println("c ==>"+c);
if( node.nxt[c-'0'] == null) {
node.cnt++; // 이 전글자의 node수 증가
node.nxt[c-'0'] = new Node(c,0);
System.out.println(node.cnt+" , c-'0':"+(c-'0'));
}
// 해당 글자를 가르킨다.
node = node.nxt[c-'0'];
System.out.println("data="+node.data+" cnt="+node.cnt);
}
}
res = 0;
searchLeaf(root);
// res 가 전화번호 수가 아니라면
if(res != N)
System.out.println("No");
else
System.out.println("YES");
}
}
public static void searchLeaf(Node node) {
if (node.cnt == 0) {
res++;
return;
}
// node의 개수가 0이 아니라면
// node자식 최대 개수10
for (int i=0; i<10; i++) {
if(node.nxt[i] != null)
searchLeaf(node.nxt[i]);
}
}
}
class Node {
char data;
int cnt;
Node[] nxt = new Node[10]; // 전화번호는 길어야 10자리
public Node(char data, int cnt) {
this.data = data;
this.cnt = cnt;
}
}