문제 링크입니다: https://algospot.com/judge/problem/read/SOLONG 트라이(Trie) 자료구조(=접두사 트리(prefix tree))를 사용하는 문제였습니다. 트라이를 간단하게 설명하자면 아래와 같습니다.정수나 실수 혹은 문자에 대해서는 BST(이진 탐색 트리)가 시간복잡도 O(logN)으로 훌륭하게 동작합니다.하지만 문자열에 대해서 BST를 사용한다면 문자열의 최대길이가 M일 경우 시간복잡도가 O(MlogN)이 되기 때문에 생각만큼 효율적이지 않습니다.트라이는 위와 같은 문제를 메모리를 희생하면서 시간복잡도를 O(M)으로 단축시켜줍니다.트라이의 중요한 속성은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사(prefix)를 얻을..
