개발조아

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제의 설명은 어렵지 않았다. 처음에는 word에 ?를 하나씩 붙여서 가능한 경우를 다 만들고 그것을 키로하고 값은 개수로 하는 딕셔너리로 만들었었다. 그리고 쿼리문을 키로해서 딕셔너리를 확인했다. word의 길이는 최대 10000자이고, 모든 가사의 길이의 합이 1백만자 이하 이므로 되지 않을까 했다. 근데 문자를 이어붙이는 과정에서 슬라이싱이 많이 들어가서 효율성 테스트에서 틀리지 않았나 싶다. 그래서 해설을 봐보니 트라이 자료구조를 사용해야한다고 한다. 문자열을 트리 구조로 저장해서 단순 비교해서 검색하는 경우 훨씬 빠르다..