목적

• 저장되어 있는 가게 이름을 기준으로 자동완성을 보여준다.
• 저장되어 있는 브랜드 이름을 기준으로 자동완성을 보여준다.
• Redis에 Trie를 만들어 저장해두어야 한다.

대략적 요구사항

빠른 응답 속도

• Trie

  • 메모리 관리 측면에서 고민해보기

• 시간복잡도

  • p : 접두어 prefix의 길이
  • n : 트라이 안에 있는 노드의 개수
  • c : 주어진 노드의 자식 노드 개수
    • 해당 접두어(p)를 표현하는 노드를 찾는데 걸리는 시간 : O(p)
    • 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드 찾기 : O(c)
    • 유효 노드들을 정렬 후 가장 인기 있는 검색어 k개 찾기 : O(clogc)

  <aside> 💡 O(p) + O(c) + O(clogc)

  </aside>

연관성

• 사용자가 입력한 단어를 기준으로 하기
  • ‘스’를 입력했으면 ‘스’로 시작하는 단어를 보여주기
  • 중간에 ‘스’가 포함되는 거까지 필요없다.
• 형태소 기준 분류는 어려워보임.

정렬

• 시스템의 계산 결과 틀
• 예를 들어서 Frequency 순