트라이(Trie)

- 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조

- 정렬된 트리 구조

- 문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름

길이가 N인 문자열 탐색의 시간 복잡도 : O(N)

apple, april, ace, bear, best

□ 구현

-  Key, Value로 이루어진 노드로 구성

Value : 이 다음에 어떤 문자를 담고 있는지 노드

isTerminal : 단어의 끝인지 아닌지 표시

class Node {
    HashMap<Character, Node> child;
    boolean isTerminal;                 // 끝을 의미

    public Node() {
        this.child = new HashMap<>();
        this.isTerminal = false;

    }
}

class Trie {
    Node root;

    public Trie() {
        this.root = new Node();
    }

    public void insert(String str) {
        Node cur = this.root;

        for(int i = 0; i<str.length(); i++) {
            char c= str.charAt(i);

            cur.child.putIfAbsent(c, new Node());   // c로 시작하는 키가 없으면 추가, 있으면 통과
            cur = cur.child.get(c);

            if(i == str.length() -1) {
                cur.isTerminal = true;
                return;
            }
        }
    }

    public boolean search(String str) {
        Node cur = this.root;

        for(int i = 0; i<str.length(); i++) {
            char c= str.charAt(i);

            if(cur.child.containsKey(c)) {
                cur = cur.child.get(c);
            } else {
                return false;
            }

            if(i ==  str.length() -1) {
                if(!cur.isTerminal) {
                    return false;
                }
            }
        }
        return true;
    }

    public void delete(String str) {
        boolean ret = this.delete(this.root, str, 0);
        if(ret) {
            System.out.println(str + "삭제 완료");
        } else {
            System.out.println(str + "단어 없음");
        }
    }

    // 재귀적 호출
    public boolean delete(Node node, String str, int idx) {
        char c = str.charAt(idx);

        if(!node.child.containsKey(c)){
            return false;
        }

        Node cur = node.child.get(c);
        idx++;
        if(idx == str.length()) {
            if(!cur.isTerminal) {
                return false;
            }

            cur.isTerminal = false;
            if(cur.child.isEmpty()) {
                node.child.remove(c);
            }
        } else {    // 지워야하는 문자를 찾기전
            if(this.delete(cur, str, idx)){
                return false;
            }
            
            // 더 이상 파생되는 단어가 없다면
            if(!cur.isTerminal && cur.child.isEmpty()) {
                node.child.remove(c);
            }
        }
        return true;
    }
    
}

 

❖ search와는 다르게 끝까지 확인 안해도됨

// 문자열 배열 strs와 문자열 prefix가 주어졌을 때
    // 문자열 배열 내에 prefix로 시작하는 단어가 있는지를 확인하는 프로그램 작성
    // prefix로 시작하는 단어가 있으면 true, 없으면 false 반환

    // 입력 strs: "apple" "april" "app" "ace" "bear" "best"
    // 입력 prefix app
    // 출력 true

    public static boolean solution(String[] strs, String prefix) {
        Trie trie = new Trie();
        for(String str:strs) {
            trie.insert(str);
        }

        Node cur = trie.root;
        for(int i = 0; i<prefix.length(); i++) {
            char c = prefix.charAt(i);

            if(cur.child.get(c) == null) {  // 반복문을 도는 도중에 null이 나오는 경우는 prefix 문자구성이 없다는 뜻
                return false;
            }
            cur = cur.child.get(c);
        }
        return true;
    }

 

❖ 시작하는 단어 바꾸기

// 문자열 배열 dictionary와 문자열 sentence가 주어졌을 때
    // sentence 내의 단어 중 dictionary의 단어로 시작하는 경우
    // 해당 단어로 변경하여 출력하는 프로그램을 작성

    // 입력 : dictionary : "cat", "bat","rat"
    // sentence = "the cattle was rattled by the battery"
    // 출력 : "the cat was rat by the bat"
    public static void solution(String[] dictionary, String sentence) {
        Trie trie = new Trie();
        for(String str:dictionary) {
            trie.insert(str);
        }

        StringBuffer sb = new StringBuffer();
        for(String word: sentence.split(" ")) {
            Node cur = trie.root;

            StringBuffer sbCur = new StringBuffer();

            for(char c:word.toCharArray()) {        // 한자리씩
                sbCur.append(c);
                if(cur.child.get(c) != null) {
                    if(cur.child.get(c).isTerminal) {
                        break;
                    }
                    cur = cur.child.get(c);
                } else {
                    sbCur = new StringBuffer(word);
                }
            }
            sb.append(sbCur);
            sb.append(" ");
        }
    }

 

❖ 한 글자만 바꾸어서 똑같은지 판단

// 문자얼 배열 strs와 targets가 주어졌을 때
    // targets 내의 단어 중 한 문자만 바꾸면 strs중의 단어가 되는지 판별하는 프로그램

    // 입력 strs : "apple" "banana" "kiwi"
    // target : "applk" "bpple" "apple"
    // 출력 : true, true, false
    public static void solution(String[] strs, String[] targets) {
        Trie trie = new Trie();

        for(String str : strs) {
            trie.insert(str);
        }

        for(String target: targets) {
            boolean result = examinWord(trie.root, target, 0, false);
            System.out.println(result);
        }
    }    

    public static boolean examinWord(Node node, String target, int i, boolean flag) {
        if(i < target.length()) {
            if(node.child.containsKey(target.charAt(i))) {  // i번째 해당하는 문자가 trie쪽에 있을때 그 다음을 재귀적으로 계속 호출
                if(examinWord(node.child.get(target.charAt(i)), target, i+1, flag)) {
                    return true;
                }
            }

            if(!flag) {
                for(char c: node.child.keySet()) {  // 밑 키 값을 다 가져옴
                    if( c!= target.charAt(i) && examinWord(node.child.get(c), target, i+1, true)) {// 한문자만다르고 나머지는 똑같은 경우
                        return true;
                    }
                }
            }
            return false;
        }

        return flag && node.isTerminal;
    }