[프로그래머스] 가사 검색 - Trie

처음 접해보는 구조의 문제였고 효율성 테스트까지 상당히 어려웠다.. 프로그래머스 가사 검색 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제는 노래 가사에 사용된 단어들 중, 특정 키워드가 포함된 문자가 몇 개 있는지 찾아내는 문제였다. 여기서 쿼리가 주어지고 그 쿼리에 맞는 단어가 몇개 있는지 찾아내는 것이다. 여기서 쿼리에서는 젤 앞이나 뒤에 "?"라는 문자가 포함될 수 있다. "?"의 개수는 자유롭다. 단, 가운데에 "?"가 포함되는 경우는 없고 앞 뒤에 전부 포함되는 경우도 없다. 그렇다면, 쿼리가 주어지고 각 쿼리당 일치하는 가사가 몇 개나 있는지 찾는 문제였다. 가장 처음에 생각했던 방식은 단순하게 O(n^3)으로 풀 수 있는 방식이었다. 그냥 모든 쿼리마다 단어들을 하나씩 ..

2020.11.24