이전 글
깃허브 주소

상황

검색 알고리즘을 원래는 movies의 데이터가 들어오면 저장을 하고 있다가 검색 input에 데이터를 넣고 submit을 할 시에 movies의 데이터와 input의 데이터를 비교하여 일치하는 것만 보여주는 방식으로 구현을 했었다.

export function searchMovie(movies) {
  return (value) => {
    const lowerValue = value.toLowerCase();
    return movies.filter((movie) => movie.title.toLowerCase().indexOf(lowerValue) !== -1);
  };
}
...
const nextMovies = searchMovies(movies)(value);

여기에 추가적으로 input의 내용이 변경될 때 마다 알아서 검색 해주는 것을 만들고 싶었다.
그래서 input이 변경할 때마다 searchMovie함수를 실행하였는데 지금은 데이터 개수가 20개여서 잘 작동하고 있지만 나중에 데이터의 개수가 많아지면 해당 방식으로는 해결이 안될 것이라고 생각을 했다.
그래서 조금 더 효율적인 것이 무엇이 있을까 생각을 하다가 Trie 자료구조를 이용하여 미리 title을 기반으로 영화들의 정보들을 저장하고 있다가 input value에 따라서 input value의 길이만큼의 시간동안 찾을 수 있을 것이라고 생각해서 그 부분을 구현을 해봤다.

Trie 구현

class Node {
  constructor(value) {
    this._childs = {}; // 다음 노드들에 대한 포인터 역할을 하고
    this._includes = value ? [value] : [];
  }
}
export class Trie {
  constructor() {
    this._root = new Node();
  }
  push(strArray, originalValue = null, node = this._root) {
    // 처음에 아무것도 안넣을때는 root를 기반으로 진행
    // str로하지 않고 arry로 해서 뒤집어서 넣고 그 다음에 저기 하는게 좋을 것 같은데
    if (node === this._root) {
      strArray = strArray.split('').reverse(); // 뒤집어서 놓고
      node._includes.push(originalValue);
    }
    // 여기서는 재귀적으로 처리하는게 좋을 것 같음
    // 언제까지 하냐면 str이 더 이상 없을때까지
    if (!strArray.length) return;

    const first = strArray.pop(); // 가장 먼저 첫번재 요소를 빼고

    if (!node._childs[first]) {
      node._childs[first] = new Node(originalValue);
    } else {
      node._childs[first]._includes.push(originalValue);
    }

    this.push(strArray, originalValue, node._childs[first]);
    return;
  }
  find(str, node = this._root) {
    // str이 주어졌을 때 찾아야 한다.
    if (node === this._root) str = str.split('').reverse();

    if (!str.length) {
      return node._includes;
    }
    const first = str.pop();
    if (!node._childs[first]) return [];

    const result = this.find(str, node._childs[first]);
    return result;
  }
}

이를 통해서 title이 일치하는 문자열들은 찾을 수 있었다.

문제점

검색을 처음부터만 가능하다

만약 title이 'abc'인 것과 'cab'가 있다고 했을 때, 'ab'를 검색하면 'abc'만 나오고 'cab'는 검색이 되지 않는다

해결방안

처음에는 이를 어찌 해결해야 할 지 아이디어가 떠오르지 않아서 튜터님께 찾아가 해당 문제에 대해서 공유하고 어떻게 해결하면 좋을지를 같이 이야기를 나눠봤다.
우선, 현재 코드 상황에서 해결할 수 있는 가장 간단한 방법은 Trie에 title을 기준으로 넣을 때 title의 부분 문자열도 함께 넣는 것이었다.

// 이전 코드
getMovies('https://api.themoviedb.org/3/movie/top_rated?language=en-US&page=1')
    .then((res) => res.json())
    .then((data) => {
      const trie = new Trie();

      data.results.forEach((v) => {
        const {title} = v;
        trie.push(title.toLowerCase(),v);
      });
      return [data.results, renderMovies(data.results), trie];
    });
// 이후 코드
getMovies('https://api.themoviedb.org/3/movie/top_rated?language=en-US&page=1')
    .then((res) => res.json())
    .then((data) => {
      const trie = new Trie();

      data.results.forEach((v) => {
        const lowerTitle = v.title.toLowerCase().replace(' ', '');
		for (let i = 0, len = lowerTitle.length; i < len; i++) {
		trie.push(lowerTitle.slice(i), v);
      	}
	  })
      return [data.results, renderMovies(data.results), trie];
    });

Trie 내 중복 저장

하나의 title을 부분 문자열로 나누면서 trie에 저장하는 것 까지는 좋았으나 중복 저장으로 인해 아래의 사진 처럼 등장하였다.

해결방안

Trie 자료구조에서 원본 내용들을 저장할 때, Set을 이용해서 중복이 되지 않게끔 저장을 하였다.

class Node {
  constructor(value) {
    this._childs = {}; // 다음 노드들에 대한 포인터 역할을 하고
    this._includes = value ? new Set([value]) : new Set();
  }
}

Set은 자바스크립트의 자료구조 중 하나로 중복을 방지하는 역할을 한다. 현재 들어오는 value의 값이 Object로 들어오는데 Object의 주소값이 들어가면서 object가 중복되지 않고 제대로 동작을 하였다.

느낀점

검색 알고리즘을 작성하는데 있어서 항상 특정 알고리즘이 정답이라고 할 수 없다라는 것을 느꼈다. 막상 조금 더 효율적이게 작성하려다가 오히려 처음에 trie의 내용들을 저장한다고 메모리를 더 많이 사용하고, 구현도 조금 더 복잡하다.
그래도 여러 방식으로 문제를 해결하려는 노력을 했다라는 것에 의의를 두고 싶다.