검색창 자동완성 기능을 붙이려고 하는데요. 처음엔 그냥 단어들을 해시맵(딕셔너리)에 다 넣어놓고 찾으면 되겠다 싶었는데, 접두사로 검색하는 게 문제더라고요.
예를 들어 사용자가 "app"까지 쳤으면 "apple", "application", "append" 이런 걸 다 뽑아줘야 하잖아요. 근데 해시맵은 키 전체가 정확히 맞아야 O(1)로 찾는 거지, "app로 시작하는 거 다 줘" 같은 쿼리는 못 하는 거 같아요. 결국 전체 단어를 다 훑어야 해서 단어가 n개면 O(n)이 되고요.
찾아보니까 트라이(trie)라는 트리 구조를 쓰라는데, 노드마다 자식 문자 맵이랑 단어 끝인지 표시(isEnd) 들고 있는 거 맞나요? 이러면 insert나 search가 문자열 길이 m에 대해 O(m)이라 단어 개수랑 무관하다고 하던데, 이게 자동완성에서 왜 유리한 건지, 그리고 대신 뭘 손해 보는 건지(메모리 같은 거요) 정리해주시면 좋겠어요.