[오늘의 코테연습장] - 백준 5052번 자바

트라이

• - 문자열을 빠르게 검색할 수 있는 자료 구조
• - 트라이의 Root노드는 항상 빈 문자열 상태
• 단어 사전을 트라이에 insert 후, 트라이를 사용하여 검색

트라이 구축하기

트라이 노드 설계

class Node
    { 
    boolean isfinish = false;
    TrieNode[] chlid = new TrieNode[10];
}

---

void insert 함수

• 단어 사전의 입력할 단어를 트라이에 삽입
• root 노드부터 시작해서 단어의 첫글자 부터 탐색
• 현재 노드의 자식이 null 일 경우 : 새로운 child를 추가
• 현재 노드의 자식이 있을 경우 : 현재 노드를 해당하는 자식 노드로 이용한다.
• 단어를 삽입한 후, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가한다.

static void insertTireNode(String word) {
    TrieNode current =root;
    for (int i = 0; i < word.length(); i++) {
        char a = word.charAt(i);
        int index = a - '0';
        if (current.chlid[index] == null) {
            current.chlid[index] = new TrieNode();
        }
        current = current.chlid[index];
    }
    current.isWord = true;
}

---

boolean serach 함수

• root 노드부터 시작해서 검색할 단어의 첫 글자부터 트라이를 탐색한다.
• 만약 현재 트라이에 입력된 노드의 child 중에 현재 입력 중인 숫자에 해당하는 자식이 있다면 현재 노드를 해당하는 자식 노드로 이동
• 만약 없다면, 검색할 단어는 트라이에 저장되지 않은, 즉 단어 사전에 존재하지 않는 단어로 처리하여 false 반환
• 탐색이 완료되었다면, 탐색된 마지막 노드의 정보를 이용한다.
• 마지막 글자이고, isfinsih가 true일 경우, 마지막 리프노드를 의미하므로 true를 출력한다.

public boolean search(String target) {

            trienode current  = root;

            for(int i = 0 ; i < target.length(); i++) {
                char a = target.charAt(i);
                int index = a-'0';
                if(current.child[index]==null) {
                    return false;
                }
                //출발 가능 조건 : root가 해당 child를 가지고 있으면 포인터는 해당 child의 주소값 가르킴
                current = current.child[index];

                if(i < target.length()-1 && current.isfinish) {
                    //마지막 글자가 아닌데, isfinish일경우 : false 반환
                    return false;
                }

            }
            return (current!=null)&&current.isfinish;
            // 마지막 글자이고, isfinsh일 경우 마지막 리프노드라는 것을 의미
            // 그렇다면 true 출력
        }