밍쎄의 코딩공간

Trie와 관련된 문제를 찾던 중에 카카오 블라인드 문제를 접하게되었다. 이번 내 부캠에서 본 코테에 대하여 멤버들과 이야기를 해봤는데 String startwith등 내장 메서드를 이용하셨다고 하셨다. 공부를 하면할 수록 점점 더 처음으로 돌아가는 것 같다...!! 흐흐 궁굼해서 다른 분의 코테를 참고하였다! https://wellbell.tistory.com/166 프로그래머스 - 자동완성 문제 (자바) programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용 wellbell.tistory.com 첫 번째 방법은 문자..

이번 코테는 처음부터 끝까지 Trie 였다. 보자마자 Trie 라는 것을 파악하는 건 성공, but 매끄럽게 코드를 구현하기는 힘들었다. -------- Trie 란? Trie는 일반적인 Tree자료구조와 같은 모양이지만 저장하는 값이 다른 형태입니다. 위와 같은 정수형 자료의 이진트리에서는 검색을 수행할 때 O(logN)의 시간 복잡도를 가지게 된다. 그러나 같은 이진트리 형태 이어도 문자열을 저장하고 있다면 문자열의 길이가 M일 때, O(M*logN)의 시간 복잡도를 가지게 된다. 이러한 문제를 해결하기 위해 Trie를 사용하는 것이다. Trie는 루트 노드는 비어있고 첫 번째 자식 노드부터 문자열의 첫 단어가 저장된다. 현재 위 그림의 Trie에 저장된 문자는 cap, code, kakao, kai..