트라이

트라이 (Trie)

문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조
정렬된 트리 구조
문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름
길이가 N인 문자열 탐색의 시간 복잡도: O(N)
생성 복잡도: O(MN)
M: 문자열 개수

트라이 형태

문자열 구성
apple, april, ace, bear, best

트라이 – 삽입 (1)

삽입 문자열: apple

트라이 – 삽입 (2)

삽입 문자열: april

트라이 – 삽입 (3)

삽입 문자열: app

트라이 – 삭제 (1)

삭제 문자열: apple

트라이 – 삭제 (2)

삭제 문자열: app

트라이 구현

Key, Value로 이루어진 노드로 구성
Key: 알파벳
Value: 자식 노드

class Node {
    HashMap<Character, Node> child;
    boolean isTerminal;
}

// 비선형 자료구조 - 트라이 (Trie)

import java.util.HashMap;

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);
            
            // 현재 노드 기준 c 문자에 해당하는 노드가 없으면 추가, 있으면 넘어감.
            cur.child.putIfAbsent(c, new Node());
            // 이어서 추가하기 위해 다음 문자 쪽으로 이동.
            cur = cur.child.get(c);

            // str 끝이면 true 체크 후 return
            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);
            
            // 해당 단어 있으면 이동, 없으면 false 반환
            if (cur.child.containsKey(c)) {
                cur = cur.child.get(c);
            } else {
                return false;
            }

            // i 가 str 끝에 도달했지만 cur 의 terminal 이 true 아니면
            // 해당 단어가 들어 있는 것은 아니므로 false 반환
            if (i == str.length() - 1) {
                if (!cur.isTerminal) {
                    return false;
                }
            }
        }
        // 위에 두 부분에 걸리지 않았으면 리턴 true.
        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);

        // 없는 단어인 경우 false 반환
        if (!node.child.containsKey(c)) {
            return false;
        }

        Node cur = node.child.get(c);
        idx++;
        
        // 단어의 가장 끝에 도달 후 삭제 결정
        if (idx == str.length()) {
            // 끝에 도달했지만 terminal true 아닌 경우
            // 해당 단어와 일치하는 것은 아니므로 false 반환
            if (!cur.isTerminal) {
                return false;
            }
            
            // 해당 단어와 일치할 경우 isTerminal 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;
    }
}

public class Main {
    public static void main(String[] args) {
        // Test code
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("april");
        trie.insert("app");
        trie.insert("ace");
        trie.insert("bear");
        trie.insert("best");
        System.out.println(trie.search("apple"));   // true
        System.out.println(trie.search("april"));   // true
        System.out.println(trie.search("app"));      // true
        System.out.println(trie.search("ace"));     // true
        System.out.println(trie.search("bear"));    // true
        System.out.println(trie.search("best"));    // true
        System.out.println(trie.search("abc"));     // false

        System.out.println();
        trie.delete("apple");
        System.out.println(trie.search("apple"));   // false
        System.out.println(trie.search("april"));   // true
        System.out.println(trie.search("appl"));    // false
        trie.delete("apple");
    }
}

true
true
true
true
true
true
false

apple 삭제 완료
false
true
false
apple 단어가 없습니다.

문자열 배열 내에 prefix 로 시작하는 단어가 있는지를 확인하는 프로그램을 작성

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

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

// 입력 strs: "apple", "april", "app", "ace", "bear", "best"
// 입력 prefix: "pre"
// 출력: false


import java.util.HashMap;

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());
            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;
    }
}

public class Practice1 {
    public static boolean solution(String[] strs, String prefix) {
        // 트라이 자료구조에 데이터 넣기
        Trie trie = new Trie();
        for (String str : strs) {
            trie.insert(str);
        }

        // prefix 체크
        Node cur = trie.root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            // 탐색을 진행하다가 하나라도 없는 문자가 있으면 false 반환
            if (cur.child.get(c) == null) {
                return false;
            }
            cur = cur.child.get(c);
        }
        return true;
    }

    public static void main(String[] args) {
        // Test code
        String[] strs = {"apple", "april", "app", "ace", "bear", "best"};
        String prefix = "app";
        System.out.println(solution(strs, prefix)); // true

        prefix = "be";
        System.out.println(solution(strs, prefix)); // true

        prefix = "pre";
        System.out.println(solution(strs, prefix)); // false
    }
}

true
true
false

해당 단어로 변경하여 출력하는 프로그램을 작성

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

// 입출력 예시
// 입력 dictionary: "cat", "bat", "rat"
// 입력 sentence = "the cattle was rattled by the battery"
// 출력: "the cat was rat by the bat"

// 입력 dictionary: "a", "b", "c"
// 입력 sentence = "apple banana carrot water"
// 출력: "a b c water"


public class Practice2 {
    public static void solution(String[] dictionary, String sentence) {
        // 트라이 구성
        Trie trie = new Trie();
        for (String str : dictionary) {
            trie.insert(str);
        }

        StringBuffer sbResult = new StringBuffer();
        // sentence 단어 별 검사
        for (String word : sentence.split(" ")) {
            Node cur = trie.root;
            StringBuffer sbCur = new StringBuffer();

            for (char c : word.toCharArray()) {
                // 문자 하나 씩 비교하며 sbCur 에 추가
                // dictionary 내에 있는 단어로 시작하는 단어가 아니면 sbCur 에 쌓인 단어 추가
                // dictionary 내에 있는 단어로 시작하면 해당 word 추가
                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);
                    break;
                }
            }

            sbResult.append(sbCur);
            sbResult.append(" ");
        }

        System.out.println(sbResult);
    }


    public static void main(String[] args) {
        // Test code
        String[] dictionary = {"cat", "bat", "rat"};
        String sentence = "the cattle was rattled by the battery";
        solution(dictionary, sentence);

        dictionary = new String[]{"a", "b", "c"};
        sentence = "apple banana carrot water";
        solution(dictionary, sentence);
    }
}

the cat was rat by the bat 
a b c water 

targets 내의 단어 중 한 문자만 바꾸면 strs 중의 단어가 되는지 판별하는 프로그램을 작성

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

// 입출력 예시
// 입력 strs: "apple", "banana", "kiwi"
// 입력 target: "applk", "bpple", "apple"
// 출력: true, true, false


public class Practice3 {
    public static void solution(String[] strs, String[] targets) {
        // 트라이 구성
        Trie trie = new Trie();
        for (String str : strs) {
            trie.insert(str);
        }
        
        // target 별 검사
        for (String target : targets) {
            boolean result = examineWord(trie.root, target, 0, false);
            System.out.print(result + " ");
        }
        System.out.println();
    }

    public static boolean examineWord(Node node, String target, int i, boolean flag){
        if (i < target.length()) {
            // 해당 문자로 시작하는 데이터가 trie 내에 있으면 그 다음 재귀 호출
            if (node.child.containsKey(target.charAt(i))) {
                if (examineWord(node.child.get(target.charAt(i)), target, i + 1, flag)) {
                    return true;
                }
            }

            if (!flag) {
                // 현재 depth 의 문자들 순회하며 비교
                for (char c : node.child.keySet()) {
                    // 문자 하나만 다르고 나머지는 true 일 때 true 반환
                    if (c != target.charAt(i) && examineWord(node.child.get(c), target, i + 1, true)) {
                        return true;
                    }
                }
            }
            return false;
        }
        // flag 가 true 인 상황에서 단어 끝일 때 true 반환
        return flag && node.isTerminal;
    }

    public static void main(String[] args) {
        // Test code
        String[] strs = {"apple", "banana", "kiwi"};
        String[] targets = {"applk", "bpple", "apple", "banan", "kiww"};
        solution(strs, targets);    // true, true, false, false, true
    }
}

true true false false true