[PS] Trie 자료구조
개념 설명
Trie는 가장 효율적인 문자열 검색 알고리즘 입니다. 다양한 문자열을 효과적으로 저장하고, 검색할 수 있습니다.
소문자로만 이루어진 문자열을 저장한다고 할 때, 위 사진의 root에서 child는 a~z까지의 26개를 가집니다. 이는 저장할 문자열의 첫 문자를 의미합니다. 이와 같은 방법으로 시간복잡도는 MlogN입니다. M은 문자열을 구성하는 문자의 수, N은 저장할 문자열의 최대 길이입니다.
insert
insert 함수를 보면 특정 문자 c가 주어지면 c - ‘a’를 통해서 index를 구합니다. 그리고 child[index]가 NULL이라면 새로운 노드를 생성합니다. child[index]->insert(key+1)은 다음 문자를 저장하는데 child[\index]에 저장된 새로운 노드가 this가 되고, 이 새로운 노드를 기준으로 다시 c - ‘a’를 구합니다.
노드를 만들어서 값을 저장하는 것이 아니라, 최소한의 size를 가지는 struct를 생성하고, NULL인지 아닌지를 따져서 찾을 수 있도록 구성합니다.
find
종료 조건은 key가 가리키는 값이 ‘\n’인 경우입니다. 즉, 널문자를 찾을 때까지 recur를 돌면서 진행합니다. 만약 널문자를 찾았다면 주어진 문자열을 모두 찾았다는 의미이므로 return true를 할 수도 있고, 문제에 따라서 return this;를 할 수도 있습니다.
문제 풀이
전화번호 목록
- 풀이 Trie* root를 생성하고 모든 문자열을 insert합니다. 만약 “a\n”를 입력하면 root의 child(0)에 new Trie()가 생성됩니다. child(0) = 임의의 주소값. 이 임의의 주소를 가지는 Node에 대해서 널문자를 insert를 시도하고 finish가 treu로 바뀝니다. 즉, 가장 마지막 문자열의 Node의 bool finish에 체크를합니다. 따라서 Trie에 입력하는 문자열의 순서는 상관없습니다.
이제 다시 처음부터 문자열을 찾아주면서 finish가 true인 경우가 있으면 일관성이 없는 경우입니다.