프로그래머스. 가사 검색

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

코딩테스트 연습 - 가사 검색

 

첫 시도:

이전에 푼 순위검색과 같이 map 자료구조를 이용한다.

frodo는 

frodo

frod?

fro??

fr???

f????

f????

이런 식으로 될수 있는 모든 경우에 대하여 맵의 key로 저장한다.

이방법은 효용성을 통과하지 못했다.

 

---

해설과 다른 분들이 푼 방법을 보고 이분탐색을 이용해 다시 풀어봤다.

원리는 다음과 같다.

 

words를 길이를 기준으로 정렬하고, 길이가 같다면 사전순으로 정렬한다

query가 "fro??"라면 ?를 a와 z로 각각 채운다.

"froaa", "frozz"

 

이분 탐색으로 "froaa"의 lower_bound의 위치를 찾는다

=> "froaa"이상의 값이 처음 나오는 지점은 "frodo" 즉 1이다.

 

이분탐색으로 "frozz"의 upper_bound의 위치를 찾는다

=> "frozz" 초과 하는 값이 처음 나오는 지점은 "kakao" 즉 4이다.

 

"fro??"에 해당하는 word의 갯수는 4-1=3 이다.

 

?가 접두에 올때

?가 앞에 올때는 word와 query 모두 뒤집어서 비교해준다.

 

 

---

TRIE 자료구조.

기본 트라이 구조 구현이랑 거의 같지만 Find 함수에서 현재 문자가 '?'면 자식의수를 리턴해주면 된다.

 

TRIE 포인터 배열을 두개 만들어서 하나에는 words의 문자열들을 저장하고,

또다른 하나에는 words의 문자열들을 뒤집어서 저장해준다. 

 

또한 words 배열의 word들은 크기별로 따로 트라이에 저장해줘야 한다.