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

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

문제

공식해설

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

문제분해 → 자료표현 → 일반화

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

구현1. 트라이 (정확성, 효율성)

참고: 프로그래머스 풀이

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

구현2. 이진검색 (정확성, 효율성) O(NlogN)

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

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

구현3. 정규표현(정확성) O(MN)

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

--

--

--

Data Engineer interested in constructing Data-Driven Architecture with Cloud Service

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
SoniaComp

SoniaComp

Data Engineer interested in constructing Data-Driven Architecture with Cloud Service

More from Medium

LeetCode — Find Peak Element

How To Install Oracle Web Logic Server In Eclipse/STS

Distributed Systems Part-3: Managing Anti-Entropy using Merkle Trees

Interval Scheduling Greedy Algorithm