카카오 : 가사검색 — 파이썬: 2020 BLIND TEST 문제 풀이
트라이: 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
문제
공식해설
원래 문자열을 이용해 만든 트라이와, 문자열을 뒤집어서 만든 트라이 두 개를 이용해야 합니다.
문제분해 → 자료표현 → 일반화
- 효율적인 문자열 검색(키워드 매치): 트라이 자료구조 이용
- ? 이 접두사로 사용할 경우 트라이 자료구조 시작점을 찾는 데 어려움이 있음: 문자열을 뒤집어서 만든 트라이를 하나 더 사용(접두사, 접미사 둘 중 하나이기 때문에)
구현1. 트라이 (정확성, 효율성)
참고: 프로그래머스 풀이
트라이의 노드에 메타데이터를 저장하고, 그 데이터를 검색에 활용한다.
구현2. 이진검색 (정확성, 효율성) O(NlogN)
참고블로그 : velog.io/@tjdud0123 (이분은 천재이신 듯.. )
쿼리랑 같은 단어들을 탐색하는데, 접두사인지 접미사인지에 따라 ?를 a와 z로 바꿔준후 그 사이에 있는 단어들을 탐색한다.
구현3. 정규표현(정확성) O(MN)
참고블로그 : velog.io/@tjdud0123
