2주차 과제 - 트라이를 사용하여 자동 완성 코드를 구현하세요.

트라이 자료 구조

이번에 해결해야 하는 과제는 트라이 자료 구조를 이용하여 검색창의 자동 완성 기능을 수행하는 로직을 구현하는 것이다. 우선 트라이 자료 구조가 무엇인지 알아야 했다.

 

Trie 란?
공간 복잡도가 큰 대신, 빠른 시간 안에 단어를 검색할 수 있는 트리의 한 종류이다.

트라이 자료구조란 쉽게 말해 문자열을 저장해서 검색할 때 활용하는 자료구조이다. 트라이 자료 구조의 경우에는 글로 설명을 듣는것보다 그림으로 이해하는것이 훨씬 직관적으로 받아드릴 수 있다.

 

Trie 자료 구조

  그림이,, 양호하지 못한점 이해하기 바랍니다...; 그림을 설명해 보자면 Trie 자료구조의 root 노드는 value 값을 따로 갖고 있지 않는다. 즉 다시 말해 root 노드가 존재하지만 빈 문자열과 같이 아무런 값도 가지지 않는것이 특징이다. 그리고 모든 간선은 의미를 가중치가 있어 이를 잘 표현하는것이 중요하다. 

 

   위 그림을 다시 문자로 풀어보자면 root node ---(h간선)---> 'h' node ---(e간선)---> 'he' node ---(l간선)--- > 'hel' node 와 같은 방식으로 데이터를 저장하게 된다. 이러한 이유로 공간 복잡도 측면에서는 효율성이 떨어질지 모르나 문자열을 검색하는데 매우 효율적이다. 간선을 표현하는 방법으로 여러가지가 있겠지만 나는 객체로 표현했다. 객체의 프로퍼티 키를 가중치 간선으로 활용했고 해당 키가 가리키는 값으로 노드를 집어넣었다. 

 

  node는 기본적으로 3가지 프로퍼티로 구성했다. 값을 담고 있어야 하기 때문에 value, 자식 노드를 가리키기 위해 child(여기서 가중치 간선을 표현), 마지막으로 단어를 반복하면서 끝까지 온전한 단어를 전부 Trie에 담은 경우에 다 담았다는 것을 표현하기 위해 complete 프로퍼티를 만들었다. (이를 통해 탐색을 하면서 complete가 true인 경우에만 데이터를 모아서 반환하게 하여 자동완성 기능을 구현)

 

트라이 자동완성 기능 구현

// 트라이 자료구조 자동완성 

class TrieNode {
    constructor(value = '') {
        this.value = value;
        this.child = {};
        this.complete = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode(); 
    }

    insert(string) { // 문자열 삽입 로직
        let currentNode = this.root;
        for(let i = 0 ; i < string.length ; i++) {
            let currentChar = string[i];
            if(currentNode.child[currentChar] === undefined) {
                currentNode.child[currentChar] = new TrieNode(currentNode.value + currentChar);
                currentNode = currentNode.child[currentChar];
            } else {
                currentNode = currentNode.child[currentChar];
            }
        }
        currentNode.complete = true;
    }

    search(string) { // 완전 탐색을 하기 위해 탐색을 시작 할 노드를 찾는 로직(autoComplete 함수를 보완)
        let currentNode = this.root;
        for(let i = 0 ; i < string.length ; i++) {
            let currentChar = string[i];
            if(currentNode.child[currentChar] === undefined) {
                return undefined;
            } else {
                currentNode = currentNode.child[currentChar];
            }    
        }
        return currentNode; 
    }

    autoComplete(string) { // 완전탐색 후 노드의 complete 프로퍼티가 true인 단어들만 배열에 담아 반환하는 함수
        let node = this.search(string);
        if(node === undefined) return null;
        let data = [];
        let queue = [];
        queue.push(node);

        while(queue.length) {
            node = queue.shift();
            if(node.complete === true) {
                data.push(node.value)
            }
            if(Object.keys(node.child).length > 0){
                for(let item in node.child) {
                    queue.push(node.child[item]);
                }
            }    
        }
        return data;
    }
}

let trie = new Trie();

trie.insert('hell');
trie.insert('hat');
trie.insert('hot');
trie.insert('hel');
trie.insert('het')
trie.insert('htt')

console.log(trie.autoComplete('')); //  ['hel', 'het', 'hat', 'hot', 'htt', 'hell']
console.log(trie.autoComplete('he')); //  ['hel', 'het', 'hell']
console.log(trie.autoComplete('t')); // 없는 문자열의 경우에는 null 반환

https://github.com/WooDaeHyun/Dev_course-first-assignment.git

GitHub - WooDaeHyun/Dev_course-first-assignment