[2018 카카오 기출] 자동완성

 

<출처: https://programmers.co.kr/learn/courses/30/lessons/17685>

---

트라이 자료 구조로 해결할 수 있는 문제입니다. 탐색을 O(L)에 할 수 있습니다. 

 

먼저 입력받은 문자열에 대해 트라이를 만들고,

 

다시 한 번 더 순회하면서 정답을 구하면 됩니다. 

 

트라이는 상태정보로 child를 가지고 있습니다.

 

특정 노드에 있는 알파벳이 insert 메서드에 호출될 때 마다 child += 1을 해줍니다.

 

즉, 자신이 완성된 뒤에도 누군가 자신을 호출했다면 그 단어는 자신과 자식관계가 되는 셈입니다.

 

자동완성 기능을 통해 더 이상 탐색을 안해도 되는 경우는 현재 탐색하는 알파벳에서

 

남은 문자열이 하나밖에 없는 경우이고, 그 때 child 값은 1입니다.

 

그래서 그 높이까지 탐색하도록 find 함수를 작성하면 됩니다.

---

<코드: https://gist.github.com/cottory/057019bd62c8dc405b7e95290d43415c>