089. Trie 자료구조

[문제] Trie(트라이, 접두사 트리) 자료구조를 제공하는 MCP 서버를 구현한다. Trie는 여러 단어를 글자 단위로 저장해 두는 자료구조로, "어떤 글자들로 시작하는 단어"를 빠르게 찾는 데 강하다. 예를 들어 "hello"가 들어 있을 때 접두사(prefix) "he"로 시작하는 단어를 물으면 "hello"를 찾아준다. 접두사란 단어의 앞부분을 말한다 — "he", "hel"은 "hello"의 접두사이지만 "lo"는 아니다. [구현할 함수] - insert(word: str) -> int word를 저장한다. 저장 후 Trie에 들어 있는 전체 단어 수를 반환한다. - search(word: str) -> bool word가 통째로 저장되어 있으면 True, 아니면 False를 반환한다. - starts_with(prefix: str) -> bool prefix로 시작하는 단어가 하나라도 있으면 True, 없으면 False를 반환한다. - autocomplete(prefix: str) -> array<string> prefix로 시작하는 모든 단어의 배열을 반환한다. 없으면 빈 배열 []을 반환한다. [입력·상태] 서버는 Trie 상태를 유지한다. 초기에는 비어 있다. [제약] - 단어와 접두사는 문자열이다. [예시] (각 예시는 초기 빈 상태에서 시작) insert("hello") -> 1 search("hello") -> True search("hi") -> False # 저장 안 됨 starts_with("he") -> True autocomplete("he") -> ["hello"] autocomplete("xy") -> [] # 해당 접두사 단어 없음