Algorithm in A..Z - Trie (Prefix Tree)

개념

위 그림은 911, 91125, 97625 저장했을 때 트리의 예시이다.

트라이는 문자열을 효율적으로 관리하기 위한 트리구조이다. 접두사를 노드에 하나씩 저장하고 접두사를 제외한 문자열을 자식 노드에 저장하는 트리구조이다. (접두사를 저장한다고 해서 Prefix Tree라고도 불림)

---

작동원리

문자열의 앞부터 차근차근 트리를 탐색하여 문자를 찾기 때문에 검색 속도는 빠르지만 각 노드별로 모든 문자를 저장할 배열이 필요하기 때문에 메모리가 많이 든다.

* 메모리 크기 : 포인터 크기 * 배열의 길이(저장하는 문자의 수) * 총 노드의 개수

---

시간 복잡도

저장 : O(L)

검색 : O(L)

---

문제

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int LIMIT = 9;

class Node {
    bool isTerminal = false;
    Node *nodes[LIMIT + 1];

public:
    Node() {
        fill(nodes, nodes + LIMIT + 1, nullptr);
    }

    ~Node() {
        for (auto &node : nodes) {
            delete node;
        }
    }

    bool insert(string &str, int key) {
        if (isTerminal) {
            return false;
        }

        if (str.size() - 1 == key) {
            isTerminal = true;
            return true;
        } else {
            if (nodes[str[key + 1] - '0'] == nullptr) {
                nodes[str[key + 1] - '0'] = new Node();
            }

            return nodes[str[key + 1] - '0']->insert(str, key + 1);
        }
    }
};

class Trie {
    Node *nodes[LIMIT + 1];
public:
    Trie() {
        fill(nodes, nodes + LIMIT + 1, nullptr);
    }
    ~Trie() {
        for (auto &node : nodes) {
            delete node;
        }
    }

    bool insert(string &str) {
        if (nodes[str.front() - '0'] == nullptr) {
            nodes[str.front() - '0'] = new Node();
        }

        return nodes[str.front() - '0']->insert(str, 0);
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<string> ve(n);
        for (auto &str : ve) {
            cin >> str;
        }


        Trie trie;
        bool isConsistency = true;
        sort(ve.begin(), ve.end());
        for (auto &str : ve) {
            if (!trie.insert(str)) {
                isConsistency = false;
            }
        }

        cout << (isConsistency ? "YES" : "NO") << "\n";
    }
}

---

문제

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

코드

class Trie {
    private var count = 0
    private val data = HashMap<Char, Trie>()

    fun put(word: String, depth: Int) {
        count++
        if (depth == word.lastIndex) {
            return
        }

        if (!data.containsKey(word[depth + 1])) {
            data[word[depth + 1]] = Trie()
        }

        data[word[depth + 1]]!!.put(word, depth + 1)
    }

    fun query(query: String, depth: Int): Int {
        if (depth == query.lastIndex) {
            return 1
        }

        return if (query[depth + 1] == '?') {
            return count
        } else {
            data[query[depth + 1]]?.query(query, depth + 1) ?: 0
        }
    }
}

class Solution {
    fun solution(words: Array<String>, queries: Array<String>): IntArray {
        val tries = Array(10001) { Trie() }
        val reverseTrie = Array(10001) { Trie() }

        words.forEach {
            tries[it.length].put(it, -1)
            reverseTrie[it.length].put(it.reversed(), -1)
        }

        return IntArray(queries.size) {
            val query = queries[it]
            if (query.first() == '?') {
                reverseTrie[query.length].query(query.reversed(), -1)
            } else {
                tries[query.length].query(query, -1)
            }
        }
    }
}

fun main() {
    println(Solution().solution(
        arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao"),
        arrayOf("fro??", "????o", "fr???", "fro???", "pro?")
    ).contentToString())
}

문제

https://programmers.co.kr/learn/courses/30/lessons/17685?language=java 

코딩테스트 연습 - [3차] 자동완성

코드

class Solution {
    public int solution(String[] words) {
        Trie trie = new Trie();
        for(String word : words) {
            trie.insert(word);
        }

        int answer = 0;
        for (String word : words) {
            answer += trie.query(word);
        }

        return answer;
    }

    static class Trie {
        private int count = 0;
        private final Trie[] data = new Trie[26];

        void insert(String word) {
            int depth = -1;
            Trie trie = this;
            while (true) {
                trie.count++;
                if (word.length() == depth + 1) {
                    return;
                }

                if (trie.data[word.charAt(depth + 1) - 'a'] == null) {
                    trie.data[word.charAt(depth + 1) - 'a'] = new Trie();
                }

                trie = trie.data[word.charAt(depth++ + 1) - 'a'];
            }
        }

        int query(String word) {
            int depth = -1;
            Trie trie = this;
            while (true) {
                if (trie.count == 1 || word.length() == depth + 1) {
                    return depth + 1;
                }

                trie = trie.data[word.charAt(depth++ + 1) - 'a'];
            }
        }
    }
}