[programmers][2020카카오공채] 가사 검색

문제 : https://programmers.co.kr/learn/courses/30/lessons/60060

---

 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다. 

 

단어들이 주어지고 접미사, 접두사를 제공하며 단어들의 개수를 묻는다. -> 트라이!

접두사에 대한 질문은 문자열의 앞에서부터 탐색하니까 일반적으로 풀 수 있는데 접미사는 뒤에서부터 탐색해야 하므로 문자들을 역순으로 만든 후 트라이를 하나 더 만든다. (접미사, 접두사를 위해 각자 1개씩 2개의 트라이 생성)

검색 키워드가 문자로 시작하는 경우(?로 끝나는 경우) 접두사를 위해 만든 트라이를 이용하여 탐색하고, 

검색 키워드가 ? 으로 시작하는 경우 해당 키워드를 역순으로 만든 뒤 접미사를 위해 만든 트라이를 이용하여 탐색한다.

 

검색 키워드를 가사들에서 찾을 때, ?가 나온 이후부터는 탐색 중인 노드에서의 모든 자식 노드들을 탐색해야 한다.

나는 요 시간 복잡도를 줄이기 위해 공간복잡도를 희생시켰다. 

보통 트라이 노드는 자식 노드들, 현재 노드가 단어의 마지막인지 여부가 있는데, 노드가 단어의 마지막인지 여부를 없애고 map을 하나 추가했다. 이 map은 key를 추가하고 있는 단어의 길이이고 value는 단어들의 개수이다.

즉, 검색 키워드 검색 시 처음 ?가 나온 경우 이후 노드들의 탐색 필요 없이 추가한 map에서 검색 키워드의 길이에 맞는 value를 반환한다.

 

시간복잡도는 가사들로 트라이를 생성시 O((가사 수) x (i번째 가사 길이))가 소요되고 검색 키워드들 검색 시 O((검색 키워드 수) x (i번째 검색 키워드 길이)) 가 소요된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/2020%EC%B9%B4%EC%B9%B4%EC%98%A4%EA%B3%B5%EC%B1%84/%EA%B0%80%EC%82%AC%20%EA%B2%80%EC%83%89.cpp