들어가며 트라이 - JavaScript를 먼저 공부한 다음 푼 문제입니다. 바로 풀리지 않거나 설명이 필요하다면 참고하는 것을 추천드립니다. 문제 설명 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다. 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다. 예를 들어, 학습된 단어들이 아래와 같을 때 go gone guild go를 찾을 때 go를 ..

트라이? 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 트라이의 특징 검색어 자동완성, 사전 찾기 등에 사용할 수 있다. 문자열을 탐색할 때 단순 비교보다 효율적으로 찾을 수 있다. L이 문자열의 길이일 때 탐색, 삽입은 O(L) 만큼의 시간 복잡도를 가진다. 자식에 대한 링크를 전부 가져야 하기 때문에 저장 공간을 많이 차지한다. JavaScript에서 사용하기 class Node { constructor(value = "") { this.value = value; this.children = new Map(); } } class Trie { constructor() { this.root = new Node(); } insert(string) { let currentNode = thi..