카카오 : 가사검색 — 파이썬: 2020 BLIND TEST 문제 풀이

트라이(Trie) 자료 구조를 이용

트라이: 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

원래 문자열을 이용해 만든 트라이와, 문자열을 뒤집어서 만든 트라이 두 개를 이용해야 합니다.

  • 효율적인 문자열 검색(키워드 매치): 트라이 자료구조 이용
  • ? 이 접두사로 사용할 경우 트라이 자료구조 시작점을 찾는 데 어려움이 있음: 문자열을 뒤집어서 만든 트라이를 하나 더 사용(접두사, 접미사 둘 중 하나이기 때문에)

참고: 프로그래머스 풀이

트라이의 노드에 메타데이터를 저장하고, 그 데이터를 검색에 활용한다.

참고블로그 : velog.io/@tjdud0123 (이분은 천재이신 듯.. )

쿼리랑 같은 단어들을 탐색하는데, 접두사인지 접미사인지에 따라 ?를 a와 z로 바꿔준후 그 사이에 있는 단어들을 탐색한다.

참고블로그 : velog.io/@tjdud0123

I will be a software architect.

I will be a software architect.