-
swexpert 3135 홍준이의 사전놀이알고리즘 문제/data structure 2018. 3. 10. 02:39반응형
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
반응형'알고리즘 문제 > data structure' 카테고리의 다른 글
백준 9202 Boggle, Trie with 할당, 비할당 그리고 Hashing 비교 (0) 2019.04.16 백준 6549 히스토그램에서 가장 큰 직사각형 (0) 2019.02.16 백준1620 나는야 포켓몬 마스터 이다솜 (0) 2018.11.23 swexpert 3135 홍준이의 사전놀이 (0) 2018.03.10 911E Stack Sorting (0) 2017.12.31