[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만까지의 배열을 만들고, 각 단어의 길이마다 몇개인지 저장
                 쿼리가 모두 ?로 구성 -> 찾지말고 리스트에 저장해둔 갯수 꺼내기 ex.5, 6

 

코드

 

주의할 점

1. 효율성 실패 - 선형구조 이용 -> 정확성 성공 효율성 성공을 위해서는 Trie구조 필요

 

2. Trie 구조 : dict 안에 dict 안에 dict 안에 dict,, 구조

구현 방법

  1) defaultdict - 코드

  2) 직접 생성

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  2) 직접 구현