Trie(트라이)
트라이는 트리 형태의 자료구조. 노드에는 알파뱃을 저장하고 다음 알파뱃으로 가는 엣지를 갖는다. 자료구조에 들어간 모든 문자열의 모든 전치사 문자열들을 저장하고 있다.
prefix : n 길이의 문자열의 전치사는 기존 문자열의 첫 문자부터 연속해서 1 이상 n 이하의 문자로 이루어진 문자열.
예시) abcdcab 의 전치사는 a ab abc abcd abcdc abcdca abcdcab
트라이는 빈 루트 노드를 가진다. (보통 null)
트라이의 개별 노드에는 해당 문자 값이 들어있고 다음 노드로 향하는 엣지를 갖는다. 엣지들은 해쉬나 배열 같은 자료구조로 구현 가능하다.
class TrieNode { char c; HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>(); boolean isLeaf; public TrieNode() {} public TrieNode(char c){ this.c = c; } }
void insert(String s) { for(every char in string s) { if(child node belonging to current char is null) { child node=new Node(); } current_node=child_node; } }
boolean check(String s) { for(every char in String s) { if(child node is null) { return false; } } return true; }
// Java implementation of search and insert operations // on Trie public class Trie { // Alphabet size (# of symbols) static final int ALPHABET_SIZE = 26; // trie node static class TrieNode { TrieNode[] children = new TrieNode[ALPHABET_SIZE]; // isEndOfWord is true if the node represents // end of a word boolean isEndOfWord; TrieNode(){ isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++) children[i] = null; } }; static TrieNode root; // If not present, inserts key into trie // If the key is prefix of trie node, // just marks leaf node static void insert(String key) { int level; int length = key.length(); int index; TrieNode pCrawl = root; for (level = 0; level < length; level++) { index = key.charAt(level) - 'a'; if (pCrawl.children[index] == null) pCrawl.children[index] = new TrieNode(); pCrawl = pCrawl.children[index]; } // mark last node as leaf pCrawl.isEndOfWord = true; } // Returns true if key presents in trie, else false static boolean search(String key) { int level; int length = key.length(); int index; TrieNode pCrawl = root; for (level = 0; level < length; level++) { index = key.charAt(level) - 'a'; if (pCrawl.children[index] == null) return false; pCrawl = pCrawl.children[index]; } return (pCrawl != null && pCrawl.isEndOfWord); } // Driver public static void main(String args[]) { // Input keys (use only 'a' through 'z' and lower case) String keys[] = {"the", "a", "there", "answer", "any", "by", "bye", "their"}; String output[] = {"Not present in trie", "Present in trie"}; root = new TrieNode(); // Construct trie int i; for (i = 0; i < keys.length ; i++) insert(keys[i]); // Search for different keys if(search("the") == true) System.out.println("the --- " + output[1]); else System.out.println("the --- " + output[0]); if(search("these") == true) System.out.println("these --- " + output[1]); else System.out.println("these --- " + output[0]); if(search("their") == true) System.out.println("their --- " + output[1]); else System.out.println("their --- " + output[0]); if(search("thaw") == true) System.out.println("thaw --- " + output[1]); else System.out.println("thaw --- " + output[0]); } } // This code is contributed by Sumit Ghosh
// 백준 5052번 전화번호 목록 import java.io.BufferedReader import java.io.InputStreamReader class trieNode( var isFinalWord: Boolean = false, // 단어의 끝 var children: HashMap<Char, trieNode> = HashMap() // 엣지의 목록 (해쉬) ) { companion object { // static val root = trieNode(false, HashMap()) fun clear() { root.children = HashMap() root.isFinalWord = false } } fun insert(word: String) { var node : trieNode = this for(c in word) { // 노드에 c 엣지가 연결되어 있으면 if(node.children.containsKey(c)) { // 노드 이동 node = node.children[c]!! } // c 엣지 없으면 else { // 노드 만들고 노드 이동 node.children[c] = trieNode() node = node.children[c]!! } } // 단어의 끝 체크 node.isFinalWord = true; } // 3가지 경우가 존재함. // 1. 기존 : 1234 , word : 123456 // 2. 기존 : 123456, word : 1234 // 3. 기존 == word fun check(word: String) : Boolean { var node : trieNode = this // 1. for(c in word) { if(node.children.containsKey(c)) { // 엣지 따라서 이동 node = node.children[c]!! } // c 엣지 없음 else { // 1. 상황 // 1. 기존 : 1234 , word : 123456 if( node.isFinalWord ) { // 현재 노드가 단어의 끝 return true; } return false; } } // 2. 상황 // 2. 기존 : 123456, word : 1234 // 3. 상황 // 3. 기존 == word return true } } // words 가 일관성 있는 목록인지?? fun solution(words: Array<String>) : Boolean { var trie : trieNode = trieNode.root for(word in words) { if(trie.check(word)) // 겹침 { // println(word) return false; } trie.insert(word) } return true; } fun main(args : Array<String>) { val br = BufferedReader(InputStreamReader(System.`in`)) repeat(br.readLine()!!.toInt()) { val n = br.readLine()!!.toInt() val words = Array(n){br.readLine()} val res = solution(words) if(res) println("YES") else println("NO") trieNode.clear() } }
레퍼런스
해커랭크 YouTube : https://youtu.be/zIjfhVPRZCg해커어스 트라이 : https://www.hackerearth.com/practice/data-structures/advanced-data-structures/trie-keyword-tree/tutorial/
긱포긱 : https://www.geeksforgeeks.org/trie-insert-and-search/
Baeldung : https://www.baeldung.com/trie-java