목록트라이 (3)
시간이 NullNull
문제를 쉽게 설명하면 1. go, gone, guild 라는 String 배열이 주어지면 이를 학습시킨다. 2. g를 입력하였을때 go와 gone가 나오므로 한번에 자동완성이 안된다. 3. 하지만 go 까지 하면 문자가 다 ( 자동 ) 완성이 되었다. 4. gon까지 입력시 gon으로 시작하는 문자는 gone 뿐이므로 gone을 완성시켜준다. 5. gu까지 입력시 gu로 시작하는 문자는 guild 이기때문에 guild를 완성시켜준다. 따라서 g + o + g + o + n + g + u 가 되어 7번 입력시 문자가 전부 자동완성 된다. 이를 풀기 위해서 지난번에 소개했던 Trie 알고리즘을 썼으며 1. 문자가 주어지면 Trie 트리를 만들고 2. 다음번에 문자 하나씩 읽으면서 ( 자동 ) 완성이 될때까지..
Trie로 검색 혹은 이 글을 보러 오신 분은 전화번호 목록에 대해서 알 것이라고 생각하고 문제 설명은 넘어가겠습니다. 그리고 sort의 경우 본인이 구현하셔도 상관없지만 이 글에서 Point의 경우 Trie 이기에 라이브러리를 활용하였습니다. ( 그리고 sort의 경우 해주지 않으면 9112 다음에 911이 들어오면 문제가 발생하여 sort 해주었습니다. ) Trie의 개념의 경우 제가 이전에 써두었던 글을 참고하시면 더 이해가 잘 가실 것 같습니다. 글 링크 따윈 저는 상남자니까 걸어두지 않을께요 이 문제는 저번 문제와 다르게 번호가 들어왔을때 ( 예를 들어, 911 이 입력되었고 다음줄에 9112가 들어오면 ) 911 때문에 isTerminal이 true 인 상황에서 현재 자식노드의 2번 이 nul..
java 트라이 알고리즘, Trie 알고리즘 등등으로 검색해서 오신 분들은 귀찮더라도 개념 자체는 다른 분들이 친절하게 그림까지 다 그려가면서 설명을 잘 해놓았기 때문에 다른 분들 글과 그림을 보면서 설명을 듣고 오시길 바랍니다! 사실 저도 엄청 검색을 해보고 많은 글을 보고 했었는데 먼가 진짜 쉽게 짜놓은 트라이 알고리즘은 없어서 이 새벽에 미친 듯이 고민해가며 트라이를 짜왔습니다. 문제는 SW Expert에 문자열 교집합이라는 문제를 참고로 하였고 사실 이 문제는 트라이로 풀면 메모리가 오버되어 절대로 풀 수가 없습니다. ㅎ.... 이거 때문에 왜 런타임 에러일까 하면서 한참을 고민했네요 B형을 준비하시는 분들은 LinkedList를 구현하는 것을 먼저 보고 오시길 추천드리며 LinkedList를 아..