트라이를 이용하라는게 아닐까싶네요

저랑 같은 곳에서 같은 날에 보신분 같네요. 그날 진짜 고생 많으셨습니다..

저는 이거 트라이 + 해시테이블 + 우선순위큐를 사용한 해법을 제시했고, 가능은 할 것 같은데 좀 비효율적이라고 답변 받았었습니다. ㅠㅠ

(처음에 별 생각 없이 있는 지식 다 꺼내보겠다고 아호코라식까지 껴서 얘기했었는데, 백링크가 여기서 필요한 이유가 있을지 반문하셨고 저도 '아차!'싶어서 철회했죠..)

따로 찾아본 결과, '증분 검색 알고리즘'이나 '검색엔진 자동완성 알고리즘' 같은걸로 찾아보면 어느 정도 나오는 것들이 있는데 여전히 잘 모르겠어요.

B-트리 같은 것들을 사용해서 하면 될 것 같다는 막연한 느낌 정도는 있는데 생각난 김에 더 찾아봐야겠네요

실제 데이터베이스가 이런식의 쿼리를 지원하니 거기에 힌트가 있을것 같습니다.

제가 알기론

B+ tree를 포함한 몇가지 자료구조를 가지고 성능 예측을 통해 어느것이 더 효율적일지 여부를 빠르게 계산해서

그것을 수행하는 방식입니다.

상당히 흥미로운 문제네요.

저라면 트라이 + 머지 소트 트리를 써서 풀 것 같습니다.