trie구조 썸네일형 리스트형 [programmers] 가사 검색 로직 1. 만약 'fro??' 을 찾는다고 하자 (1) 길이가 5 인 곳으로 들어간다 (2) 거기서 f 로 들어간다. cnt에는 f로 시작하는 단어가 4개있다는 것을 저장한다. (3) r 로 들어간다. cnt에는 r로 시작하는 단어가 4개 있다는 것을 저장한다. (4) o 로 들어간다. cnt에는 o로 시작하는 단어가 3개 있다는 것을 저장한다. (5) ? 를 만나면 cnt 를 리턴. (6) fro 로 시작하면서 길이가 5인 단어는 마지막에 저장된 3개이다. 2. ** 문제점 : 이렇게 하면 효율성 3번에서 틀린다! why? 쿼리가 모두 ?로 구성된 경우 있음 ** 해결책 : 단어의 길이가 최대 1만까지이므로 1만까지의 배열을 만들고, 각 단어의 길이마다 몇개인지 저장 쿼리가 모두 ?로 구성 -> 찾지말.. 더보기 이전 1 다음
