Trie2 [자료구조] Trie 트라이 트라이 (Trie) retrieval Tree에서 온 단어 문자열들을 트리 구조로 저장하여 O(log n) 속도로 빠르게 문자열을 탐색할 수 있게 해준다. 알고리즘 문제에선 주로 문자열의 '접두어', '~로 시작하는', '접미어', '~로 끝나는' 등의 키워드가 나오는 접두어, 접미어 판별 문제에서 사용된다. ※ 참조 문제 코딩테스트 연습 - 가사 검색 programmers.co.kr 자바로 트라이 구현하기 1. 노드 (Node) 클래스 import java.util.HashMap; public class Node { //해당 node 밑의 서브트리 총 node 개수 (옵션 : 즉 필요에 따라 넣는 요소) int count = 0; // isLast = true면 해당 문자열 존재 boolean isLa.. 2020. 8. 26. [알고리즘] 전화번호 목록 (백준 5052번) 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 문자열 처리 문제인데 전화번호들의 일관성을 유지하려면 '한 번호가 다른 번호의 접두어인 경우가 없어야 한다' 라고 되어있다. 즉 911, 9112584 같은 경우엔 일관성이 없는 경우이다. 접두어 판별문제인만큼 Trie를 사용해야한다. Trie 자료구조에 관한 것은 알고리즘 설명 카테고리에 올라와 있을 것이다. Trie 클래스와 Node 클래스를 만들고 Trie 클래스에 String을 삽입하는 insertString() 메서드와 일관성 있는지 판별하는 isConsi.. 2020. 8. 26. 이전 1 다음
