📊 트라이를 이용한 자동완성 기능 구현

프로그래머스 프론트엔드 데브코스 2주차 과제인 트라이 자료구조를 이용한 자동완성 기능을 구현해보았다.

💡 자동완성 기능이란 ?

=> 사용자가 입력한 검색어로부터 추천된 검색어 리스트를 보여주는 것

자동완성 기능을 구현하기 전, 우선 트라이 자료구조에 대해서 알아보자.

---

📌 트라이

트라이란 ?

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조이다.

JS에서 트라이의 구현

=> 트리 구조를 구성하는 노드들을 인접 리스트 형태로 구현

class Node{
    constructor(value=""){
        this.value = value; // 노드에 들어갈 문자 값 
        this.children = new Map();  // 연결된 다음 노드들의 문자값 ?    
        // 
    }
}

• 루트 노드의 value는 ""이고, children이라는 map 자료구조를 가지고 있고, 이 children의 각 entry들의 key 값은 간선을 의미하고, value 값이 연결된 노드를 의미한다.

  => 위 예시 그림에서 t 노드의 value는 t이고, children은 map 자료구조로 2개의 entry를 가지고 있으며, 이는

  {"e" : value=te인 node}

  {"o" : value=to인 node } 이다.

자세한 구현 내용은 다음 목차에서 살펴보자 !

---

📌 트라이를 이용한 자동완성 기능 구현

내가 이번에 구현하고자 하는 자동완성의 기능은 아래와 같다.

사용자가 입력한 검색어로부터 시작될 수 있는 다른 검색어들의 목록을 검색어의 길이 순으로 보여준다. 예를 들어, plz, proud, program, picnic, programmers 의 검색어들이 등록되어 있고 사용자가 pro를 입력한다면 => proud, program, programmers의 단어들을 보여주는 것이다.

이러한 기능을 트라이를 바탕으로 구현한 과정을 알아보자.

1. 트라이 구현을 위한 Queue, Node 클래스 구현

class Queue { // level order traversal을 위한 Queue 구현 
    constructor(){
        this.queue = [];
        this.front = 0;
        this.back = 0;
    }

    enqueue(value){ 
        this.queue[this.back++] = value;
    }

    dequeue(){   
        const value = this.queue[this.front];
        delete this.queue[this.front]; // 
        this.front += 1;
        return value;
    }

    size(){
        return this.back - this.front;
    }
}

class Node {
    constructor(value="", isWord=false){
        this.value = value;
        this.children = new Map();
        this.isWord = isWord; // node의 value값이 등록된 단어인지 
    }
}

Array를 이용해 Queue를 구현하고, 트라이를 구성하는 노드에 해당하는 Node 클래스도 구현해주었다.

Node 클래스를 구현할 때, node의 값을 나타내는 value 프로퍼티와 자식 node의 집합인 children 프로퍼티 뿐만 아니라, 해당 node의 value가 등록된 단어인지를 나타내는 isWord 프로퍼티도 함께 선언해주었다.

isWord 프로퍼티를 선언해준 이유는 ?

위와 같은 트라이 구조에서 유저가 만약 t를 입력했다면 ?

t의 자식 노드들은 to, te, tea, ted, ten이 있지만이 중에서 실제 단어인 tea, ted, ten, to 만 출력하고, te는 단어를 입력하는 과정에서 트라이에 추가되긴 했지만, 특정 단어의 일부분이기 때문에 출력하지 않으려고 한다.

따라서, 단어들을 등록할 때 isWord를 true로 설정해주고 isWord가 true인 단어들만 출력해주려고 한다.

2. 트라이 구현 => insert, find 메서드

class Trie {
    constructor(value=""){
        this.root = new Node(value);
    }

    insert(string){
        let currentNode = this.root;

        for(const char of string){
            if(!currentNode.children.has(char)){
                const charForInsert = currentNode.value + char; // 다음 node에 입력될 value값
                currentNode.children.set(
                    char,
                    new Node(charForInsert, charForInsert === string)
                );
            }

            currentNode = currentNode.children.get(char);
        }
    }
    
    find(string){ // string에 해당하는 node를 반환
        let currentNode = this.root;

        for(const char of string){
            if(!currentNode.children.has(char)){
                return null;
            }
            currentNode = currentNode.children.get(char);
        }
        return currentNode;
    }
}

insert 메서드

사용자에게 검색어를 추천해주기 위한 리스트에 새로운 단어를 추가하는 메서드이다. 동작 과정을 이해하기 위해 아래 그림에서 toss라는 단어를 등록하는 예시를 생각해보자.

insert("toss");

1. currentNode를 root 노드로 설정한다.

2. 입력된 문자열 toss의 각 문자 t, o, s, s를 하나씩 for문으로 돌 것이다.

   • t

     => 현재 currentNode의 children 프로퍼티가 t라는 key 값에 해당하는 value를 가지고 있는지 검사하고, 현재는 있기 때문에 currentNode를 해당 children에 들어있는 node중 key 값 t에 해당하는 node로 바꿔주고, 이 node는 value 값으로 t를 가질 것이다.

   • o

     => 현재 currentNode의 children 프로퍼티가 o라는 key 값에 해당하는 value를 가지고 있는지 검사하고, 현재는 있기 때문에 currentNode를 해당 children에 들어있는 node 중 key 값 o에 해당하는node로 바꿔주고, 이 node는 value 값으로 to를 가질 것이다.

   • s

     => 현재 currentNode의 children 프로퍼티가 s라는 key 값에 해당하는 value를 가지고 있는지 검사하고, 현재 노드인 to는 자식 노드가 없기 때문에 현재 노드의 children map 객체에 { key : "s" , value : Node() }인 요소를 추가한다.

     여기서 이 node는 등록하려는 단어 toss가 아니기 때문에 node의 isWord 프로퍼티는 false로 설정해준다. 등록하려는 단어인지 판단하기 위해, 등록하려는 단어 string과 노드의 value 값이 될 currentNode.value + char 값을 비교해줬다.

     const charForInsert = currentNode.value + char; // 다음 node에 입력될 value 값
     
     currentNode.children.set(
         char,
         new Node(charForInsert, charForInsert === string) 
     );

   • s

     위 s와 같은 과정을 거치고, 여기서는, isWord = true 인 값으로 노드가 추가된다.

3. 자동 완성 기능 구현

levelOrder(node){ // level order
    const q = new Queue();
    q.enqueue(node);

    while(q.size()){
        const currentNode = q.dequeue();
        if(currentNode.isWord){ // 등록된 단어만 출력
            console.log(currentNode.value); 
        }

        for(let key of currentNode.children.keys()){
            q.enqueue(currentNode.children.get(key));
        }
    }
}

autoComplete(string){
    // string을 가지고 있는 node를 찾아서
    let node = this.find(string);
    // node부터 순회 시작 
    console.log(`검색어 : ${string}`); 
    this.levelOrder(node);
}

leverOrder 메서드

사용자가 입력한 단어로부터 생성될 수 있는 추천 검색어들을 길이순으로 출력해 줄 것이기 때문에 Queue를 이용한 lever order 순회를 구현했다.

입력된 node부터 자식 노드들을 level order로 순회하면서 등록된 단어일 때만 출력해주었다.

if(currentNode.isWord){ // 등록된 단어만 출력
    console.log(currentNode.value); 
}

autoComplete 메서드

1. 우선 입력된 문자열 string을 가지고 있는 node를 찾고
2. 이 node를 시작으로 leverOrder 메서드를 실행하면

자동완성 기능을 구현할 수 있다.

4. 단어 등록 및 자동 완성 테스트

const trie = new Trie();
trie.insert("pro"); // 출력 x
trie.insert("proto"); // 출력 x
trie.insert("prou"); // 출력 x
trie.insert("protorype");
trie.insert("programmers");
trie.insert("primary");
trie.insert("proud");
trie.insert("picnic");
trie.insert("plz dm");

trie.autoComplete("pro");

내가 기대한대로 잘 동작하는 것을 확인할 수 있다 !

---

🙇🏻‍♂️ 참고 및 이미지 출처

• hysong.log