cs-js-11-자료구조-트라이(Trie)

SeungWoo Yoo ·2023년 2월 7일

DataAlgo

JS-자료구조-알고리즘

목록 보기

11/16

1. 트라이(Trie)

검색 엔진에서 자동완성을 하려면 어떻게 해야할까요?

Data Structure_11_1

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
e.g. 검색엔진 연관 검색어

1.1 트라이 특징

검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
문자열을 탐색할 떄 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
L이 문자열의 길이일 떄 탐색, 삽입은 $O(L)$ 만큼 걸린다.
대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

1.2 Trie 생성하기

1.2.1 트라이 구조

루트는 비어있다.
각 간선(링크)은 추가될 문자를 키로 가진다.
각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

Data Structure_11_2

Data Structure_11_3

Data Structure_11_4

2. 구현

class Node {
  constructor(value = '') {
    this.value = value;
    this.children = new Map();
  }
}

class Trie {
  // 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);
    }
  }
  
  // 문자열이 존재하는지 체크
  has(string) {
    let currentNode = this.root;

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

const trie = new Trie();
trie.insert('cat');
trie.insert('can');
console.log(trie.has('cat')); // true
console.log(trie.has('can')); // true
console.log(trie.has('cap')); // false

2. 트라이 실습 : 자동완성

2.1 문제

https://school.programmers.co.kr/learn/courses/30/lessons/17685

2.2 풀이

2.2.1 문제 유형

사실 문제 이름부터 자동완성이기 때문에 바로 Trie를 떠올릴 수 있습니다. 거기에 문제 내용까지 살펴보면 자동완성 기능이 되어야 최소 입력 글자를 알 수 있기에 이 문제에선 Trie가 가장 효율적인 자료구조라는 것을 알 수 있습니다.

2.2.2 풀이

Trie 구조를 만들면서 하위에 어떤 문자들이 있는지 미리 알아야 셀 수 있습니다. 예를 들어, guild를 찾을 때 gu만 입력해도 된다는 것을 알기 위해 Trie 구조에 해당 정보들을 넣어놔야 합니다.

다음과 같이 Trie 구조를 구성할 수 있습니다.

"go"를 넣는다.
루트의 자식 노드로 "g"를 추가한다. 이때 "g" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
("g", 1)과 같은 형태로 상태를 저장한다.
"g"의 자식 노드로 "o"를 추가한다. 이때 "o" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"o" 노드는 카운팅이 1이 된다.
"gone"을 넣는다.
루트의 자식 노드로 "g"를 추가한다. 이때 "g" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"g" 노드는 카운팅이 2가 된다.
"g"의 자식 노드로 "o"를 추가한다. 이때 "o" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"o" 노드는 카운팅이 2가 된다.
"o"의 자식 노드로 "n"을 추가한다. 이때 "n" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"n" 노드는 카운팅이 1이 된다.
"n"의 자식 노드로 "e"을 추가한다. 이때 "e" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"e" 노드는 카운팅이 1이 된다.
"guild"를 넣는다.
루트의 자식 노드로 "g"를 추가한다. 이때 "g" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"g" 노드는 카운팅이 3가 된다.
"g"의 자식 노드로 "u"를 추가한다. 이때 "u" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"u" 노드는 카운팅이 1이 된다.
"u"의 자식 노드로 "i"를 추가한다. 이때 "i" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"i" 노드는 카운팅이 1이 된다.
"i"의 자식 노드로 "l"를 추가한다. 이때 "l" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"l" 노드는 카운팅이 1이 된다.
"l"의 자식 노드로 "d"를 추가한다. 이때 "d" 노드에 단어가 추가되었음을 알리기 위해 카운팅을 해준다.
"d" 노드는 카운팅이 1이 된다.

그럼 Trie 구조가 다음과 같이 구성됩니다.

    [3, "g"]
      /  \
[1, "u"] [2, "o"]
   |        |
[1, "i"] [1, "n"]
   |        |
[1, "l"] [1, "e"]
   |
[1, "d"]

Trie 구조가 완성되었다면 이후 각 단어들을 찾으며 카운팅이 1이라면 이후 글자를 입력하지 않아도 된다는 것을 알 수 있기 때문에 그 지점에서 카운팅을 멈추면 됩니다.

2.2.3 전체 코드

위 알고리즘을 구현하면 다음과 같습니다.

function makeTrie(words) {
  const root = {}; // 먼저 루트 노드를 설정할 변수를 만든다.
  for (const word of words) { // Trie를 구성하기 위한 루프를 돌린다.
    let current = root; // 루프부터 시작
    for (const letter of word) { // 단어의 글자를 하나씩 춫출한 후
      // 값을 넣는다. 리스트의 첫 번째 값은 학습된 단어가 몇 개인지를 카운팅하고 
      // 두 번째 값은 트리 구조로 이용할 노드 값으로 사용한다.
      if (!current[letter]) current[letter] = [0, {}];
      current[letter][0] = 1 + (current[letter][0] || 0); // 카운팅을 위해 1 더해준다.
      current = current[letter][1]; // current는 letter에 해당되는 노드로 이동한다.
    }
  }

  return root; // 반환
}

function solution(words) {
  let answer = 0;
  const trie = makeTrie(words); // Trie 자료구조를 만들어준다.

  for (const word of words) { // 입력받은 수 만큼 루프
    let count = 0; // 카운팅을 위한 변수
    let current = trie; // 루트부터 시작
    for (const [index, letter] of [...word].entries()) {
      count += 1;
      if (current[letter][0] <= 1) { // 단어가 하나 이하로 남을 경우 종료
        break;
      }
      current = current[letter][1]; // 다음 노드로 이동
    }
    answer += count; // 카운팅을 더해준다
  }
  return answer; // 반환
}