데브코스를 열심히 수강하면서 바닐라 자바스크립트와 친해질 수 있는 기회를 많이 얻게 되어서 순수 자바스크립트로 약 3주간 다양한 기능들을 만들어 보고 있다. 평소 React나 NextJs같은 프레임워크만으로 복잡한 기능들을 구현하다 보니, 짜맞춰진 프레임워크와 라이브러리의 문법 사용법에만 집중하지 어떻게 이를 논리적으로 구현해야 하는지에 대해 고민을 소홀히 했던 나날을 보냈었던 것 같다.
그래서 이번에 가지게 된 3주라는 기간이 굉장히 소중하고, 최대한 외부 레퍼런스를 찾아보는 것을 자제하면서 구현을 하나부터 열까지 한땀한땀 해보고자 하였다.
첫 과제로 마주하였던 것은 바로 자동완성 구현하기이다.
자동완성은 평소 검색 포탈 사이트에서 정말 많이 사용하고 자주 보지만, 직접 만들어 서비스나 프로젝트에 적용해본 적은 없어서 이 기능을 순수 자바스크립트만으로만 만들려고 하다 보니까 굉장히 막막했던 것 같다.
하지만 백문불여일견... 걱정만 하다 보면 제대로 할 수 없다. 직접 구현해보자! 👊
1. 트라이 자료구조
자동완성 검색기능에서 가장 많이 사용하고, 이를 구현하기 위해서 필수로 이해해야 하는 것은 트라이 자료구조이다. 일단 트라이 구조를 잘 나타내는 아래 자료 사진을 보자.
자동완성검색 기능을 구현하기 위해서는 문자열을 제대로 다룰 수 있어야하는데, 이를 효율적으로 다루기 위해 존재하는 자료구조이기 때문에 적절하게 사용한다면 자동완성 기능을 구현할 수 있다. 자동완성 뿐만 아니라, 사전 검색 기능도 효율적으로 사용할 수 있다는 것이 큰 장점이기 때문에 주로 문자열과 관련된 곳에 자주 사용된다.
트라이 자료구조 구현하기
먼저, 트라이 자료구조에 저장해야 하는 것들을 나열해보자.
- 자기 자신에 대한 값을 담은
value부분 - 자식 노드를 담을 수 있는
children
즉, 트리에 대한 노드를 먼저 생성해주어야 한다.
class Node {
constructor(value="") {
this.value = value;
this.children = new Map();
}
}Map 객체 자료형을 이용하여, 객체를 조금 더 쉽게 관리할 수 있도록 한다. 자식노드는 Map 객체로 생성하였기 때문에 그와 관련된 has, set, get과 같은 메서드도 사용할 수 있다.
이제 이러한 노드를 트리에 하나하나 차곡차곡 쌓도록 해야 한다. 트라이 자료구조는 아무 값도 없는 루트에서 시작하여 하위 노드(자식 노드)로 가면 갈 수록 문자열을 점점 완성해 나가는 구조로 이루어져 있다. 클래스 문법을 이용하여 Trie 자료구조를 구현해보자.
class Trie {
constructor(){
this.root = new Node();
}
insert(string){
let currentNode = this.root;
for(const char of string){
if(!currentNode.children.has(char)){
currentNode.children.set(
char,
new Node(currentNode.value + char)
);
}
currentNode = currentNode.children.get(char);
}
}
}여기서 집중하여 봐야 하는 것은 바로 insert 메서드이다.
위에서 언급했듯이 노드들은 현재 Map 메서드로 관리되고 있기 때문에 그에 맞게 자료형을 맞춰 주어야 한다.
root 노드부터 시작하여, string의 인덱스를 하나하나 검사한다.
예를 들어, 홍대입구 라는 문자열을 받게 되면,
홍 대 입 구 이렇게 작은 문자열 단위로 쪼갠다. 이후, 자식 노드에 일치하는 문자열이 없다면 set 메서드를 이용하여 현재 노드의 자식노드를 문자열 char 를 Key로 지정하고, 값으로는 루트노드부터 계속하여 문자열을 더해 자식노드의 value로 저장하면서 완성된 문자열 형태를 저장해주는 것이다.
한성대입구역 한성백제역 두가지가 존재하는데, 이를 저장한다고 가정해보자. 한성까지의 정보가 트리에 존재한다고 생각한다면 한 - 성 그리고 이에 대한 자신 노드들이 key는 각각 대, 백 이고, value는 Node로 지정되어 Node에 대한 value값은 한성대, 한성백 으로 저장되어 있으며 Node에 대한 children역시 Map 객체로 저장된 것이다.
이러한 방식으로 트라이 자료구조를 만들 수 있으며,
지하철역을 바탕으로 트라이 자료구조를 만들어야 하기 때문에 공공데이터를 json 형식으로 다운받아 필요한 역 이름만 가져와 쓸 수 있도록 모듈을 생성했다.
const station_name = trainData.map((station) => station.station_nm);
const trie = new Trie();
station_name.forEach((station) => {
trie.insert(station);
});2. 자동완성 기능 구현하기
자 이제 트라이 자료구조를 만들었으니, 입력받는 Input값에 대한 이벤트를 처리할 수 있는 메서드를 생성해보자.
먼저 순수 Html만으로 DOM을 조작해야 하므로,
const inputBox = document.querySelector('.inputBox');
const keywords = document.querySelector('.keywords');이벤트를 지켜볼 input박스와 자동완성된 단어들이 뜰 수 있는 공간인 keywords DOM을 불러온다.
inputBox.addEventListener('input', checkInput);그리고 이벤트 리스너를 등록하여 Input 이벤트가 일어날때마다 콜백함수가 실행되도록 한다. 사실 디바운싱 처리를 해서 input값에 대한 처리도 해야 한다. 이 점은 추후 코드리뷰 이후 디바운스에 대해서 깊게 공부한 후 구현해보고자 한다.
자동완성 로직을 수행할 메서드를 생성해주어야 한다.
이 기능은 class로 관리를 하도록 코드를 작성했다.
class AutoComplete {
constructor(trie){
this.root = trie.root;
this.wordlist = [];
}
print(string){
this.wordlist =[];
const queue = new Queue();
let currentNode = this.root;
for (const char of string){
if(currentNode.children.has(char)){
currentNode = currentNode.children.get(char);
}
}
currentNode.children.forEach((node)=> {
queue.enqueue(node);
})
if (currentNode.children && currentNode.children.size === 0){
if (string.length > currentNode.value.length)
return
queue.enqueue(currentNode.value)
}
while(queue.size){
currentNode = queue.dequeue();
if (currentNode.children && currentNode.children.size === 0){
this.wordlist.push(currentNode.value);
}
else {
currentNode.children.forEach((node)=> {
queue.enqueue(node);
})
}
}
return this.wordlist
}
}전체 코드이다. 하나하나 뜯어보면서 어떤 의도로 코드를 작성했는지 알아보자.
현재 자동완성도 트라이 자료구조를 넘겨받아 루트로부터 Level order방식으로 모든 단계(Level)의 트리 노드를 순회할 수 있어야 한다.
Level order를 구현하기 위해서는 큐 자료구조를 이용하여 배열에 들어온 순서대로 노드를 확인해주어야 하므로, 큐 자료구조도 따로 구현해주었다.(자바스크립트는 큐 언제 지원해주나!! ㅠㅠ)
class Queue {
constructor(){
this.queue = [];
this.front = 0;
this.rear = 0;
this.size = 0;
}
enqueue(node){
this.size += 1;
this.queue[this.rear++] = node;
}
dequeue(){
const value = this.queue[this.front];
delete this.queue[this.front];
this.front += 1;
this.size -= 1;
return value;
}
}큐에 대한 자료구조는 쉬우니까 넘어가도록 하고..
루트노드부터 탐색하며, 조건에 맞는 결과가 발견되면 그 즉시 wordlist에 추가하고, print메서드를 통하여 정답을 반환하는 것으로 마무리지을 수 있다.
for (const char of string){
if(currentNode.children.has(char)){
currentNode = currentNode.children.get(char);
}
}
currentNode.children.forEach((node)=> {
queue.enqueue(node);
})입력받은 string의 배열을 하나씩 돌면서 현재 루트노드의 자식이 그러한 문자열이 있는지 검색하는 과정이다. 만약 존재한다면 해당 노드까지 내려가서 현재 노드를 바꾸어준다. 이전에 예시로 든 것처럼
한 만을 입력하면 한강진역 한양대입구역 한성대입구역 등등.. 굉장히 많은 자식 노드들의 value들이 있을 것이다. 그런데 사용자가 한성을 입력하게 되면 한성대입구 한성백제 이렇게 노드의 범주가 줄어드니 currentNode를 조건에 해당하는 children으로 바꾸어 주는 것이다.
이후, chilrden 노드를 순회하면서 그를 큐에 넣는다.
이 때, 문제점이 하나 생겼다.
자기 자신을 입력하였을 때에도 그에 대한 자동완성 결과가 나와야 하는데, 자신의 자식 노드들만 큐에 넣어주다 보니까, 이를 고려하지 못한 것. 만약 자기 자신이 string으로 나오게 된다면 이를 대응할 수 있도록 해주자.
if (currentNode.children && currentNode.children.size === 0){
if (string.length > currentNode.value.length)
return
queue.enqueue(currentNode)
}자기 자신을 입력하게 될 경우에는 자식노드가 한개도 없는 끝이므로, Map 이 가지고 있는 요소의 size가 0이라면, 자기 자신을 큐에 추가해주는 코드를 작성한다. 단, 한성대입구역역역 이렇게 입력해도, 자식노드가 빈 객체로 인식되므로, 입력된 문자열의 길이가 현재 노드의 값보다 길다면 큐에 이를 추가해주지 않는다.
이제 큐에 정답을 담았으니 값을 반환하기만 하면 된다! 가벼운 마음으로 마무리해보자.
while(queue.size){
currentNode = queue.dequeue();
if (currentNode.children && currentNode.children.size === 0){
this.wordlist.push(currentNode.value);
}
else {
currentNode.children.forEach((node)=> {
queue.enqueue(node);
})
}
return this.wordlist
}이제 큐에서 노드를 하나씩 꺼내준다. 만약 자식이 존재하지 않는 마지막 레벨의 노드라면 정답에 그 노드의 value (ex.홍대입구)를 넣어주고, 끝이 아닌 노드가 반환되면 (ex.홍대입) 그 노드의 자식을 모두 찾아 다시 큐에 넣어준다.
마지막으로 wordlist를 반환해주면 자동완성이에 대한 정답만이 담긴 리스트를 반환받을 수 있다.
이제 이를 돔에 보여줄 일만 남았다.
돔에 랜더링해주는 메소드를 작성해주자.
inputBox.addEventListener('input', checkInput);
const checkInput = () => {
const inputvalue = inputBox.value;
if (inputvalue === "") {
keywords.textContent="";
return;
}
loadAutoFill(inputvalue);
}input값을 체크해주는 콜백함수이다. 만약 사용자가 아무것도 입력하지 않았다면, keywords에 빈 문자열을 넣어준다. 만약 사용자가 입력한 게 있다면 그 문자열과 함께 아래 메서드를 수행한다.
const loadAutoFill = (input) => {
const arr = autocomplete.print(input)
if (arr && arr.length > 60){
keywords.textContent="찾는 역이 없습니다."
return;
}
fillHTML(arr);
}입력받은 값을 아까 만든 Autocomplete 객체의 메서드에 넘겨주어 정답만이 담긴 arr를 받는다. 만약 arr의 길이가 60개 이상이라면, 존재하는 많은 역들이 매칭이 되지 않는 것이므로 찾는 역이 없다는 안내 문구를 반환하고, 사용자가 올바른 역 이름을 입력하게 된다면 fillHTML 메서드를 통하여 진짜로 랜더링을 진행한다.
const fillHTML = (arr) => {
keywords.textContent="";
const $ul = document.querySelector('ul');
if (!arr){
return
}
$ul.innerHTML =
`
${arr && arr.map(el =>
`<li class='word-element'>${el}역</li>`).join('')}
`
}랜더링이 다시 될 때마다 자동입력된 부분들을 초기화시켜주어야 하므로 메서드의 첫부분에는 keyword 박스를 비워줄 수 있도록 하였다. 이후, map을 이용하여 역을 하나하나 랜더링해준다. 여기서 주의해야 할 점은 map을 통해 반환된 배열을 join메서드로 문자열화 시켜주어야 제대로 랜더링된다!
이렇게 해서 완성된 바닐라자바스크립트로 자동완성 기능 만들기이다~!!
오랜만에 프레임워크 없이 만들러니까 초반에는 많이 헤맸는데, 자바스크립트의 메서드, 자료형에 대해서 꼼꼼히 복습하는 기분이 들어 매우 상쾌하다. 다음에는 어떤 걸 만들어 볼까!!!
이분탐색 대신 트라이를 사용하신 이유가 있으실까요?