티스토리 뷰

반응형

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS

홍준이의 사전놀이 

난이도 : D5 
(하지만 기본적인 Trie data structure implemetation이었다)



트라이 자료구조를 통해 수행했다.


만약 트라이가 뭔지 모른다면 제가 정리한 포스팅이 있습니다 클릭 클릭


온라인 커뮤니티에서 들었는데, 가장 현명했던 방법은 단어를 insert 하면서 각 노드를 cnt++ 해주는것이 나중에 임의의 문자열 S에 해당하는 단어가 몇개있는지 체크해주는 것이였다. 

나는 재귀를 통해 word 를 체크하였고, 그 방법은 최악의 경우의 연산수는 26^10 ( S<= 10 ) 이기 때문에 굉장한 수의 연산이였기 때문이다.

현명한 방법을 알려주신 익명의 유저님, 감사합니다.




소스보기 (main + user 를 합쳤다)

https://github.com/ingyeoking13/algorithm/blob/master/swex/3135.cc

반응형