Trie

코딩 테스트 시 필요한 이유

트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조이다.

 

대학 수업 시간에 Tree의 문자열 형태라고 공부하긴 했지만 그 당시 난이도가 너무 높고 수업에서 중요한 비중을 두지도 않았기에 그냥 넘겼다.

그런데 카카오 코딩 테스트 4 Level을 풀다 보니 문자열 관련 문제는 대부분 Trie나 DP를 사용해야지만 시간 부족 문제가 발생하지 않았다.

 

DP는 아이디어의 문제라고 하더라도 Trie는 개념을 모른다면 사용할 수조차 없었다.
따라서 Trie에 대해서 자세히 알아보고 직접 구현까지 해보기로 하였다.

---

트라이 작동 원리

문자열 집합 ["word","war","warrior","world", "go", "gone", "goto"]을 트라이로 구현한 것이다. 

 

트라이는 1개 문자열에서 현재 문자의 다음에 나오는 문자가 현재 문자의 자식 노드가 되는 방식으로 만든 Tree를 말하며 위 사진에서 초록색으로 칠해진 노드는 문자열의 끝을 의미한다.

즉, GONE을 보면 O와 E에 초록색이 칠해져 있으므로 GO라는 단어와 GONE이라는 단어 모두 존재함을 알 수 있다. 

 

위 사진을 보면 트라이의 속성이자 코딩 테스트에서 많이 사용하는 이유가 나오는데 바로 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면 문자열의 접두사를 얻을 수 있다는 것이다.

 

나는 "WARRIOR"라는 단어를 Trie에 저장했을 뿐이지만 "WAR"이라는 접두사를 가짐을 3번 Node를 이동하면 알 수 있게 되는 것이다.

---

사용 이유

Trie의 사용 이유는 당연하게도 실행 시간의 감소일 것이다. 그렇다면 어느 정도의 시간이 감소될까?

 

2개의 문자열을 비교하기 위해선 문자열의 길이(M)만큼의 시간 복잡도가 생긴다.

탐색할 때 주로 활용하는 이진 탐색 트리를 문자열 List에 적용한다면 특정 문자열을 검색하는 총시간은 O(Mlog(N))이 될 것이다.

 

트라이는 중간 문자열을 모두 이진 트리에 넣어둔다.

따라서 가장 긴 문자열의 길이를 M, 총 문자열 개수를 N이라 할 때 탐색 및 삽입 시 O(M)의 시간 복잡도밖에 가지지 않는다.

 

이 부분은 개인적인 사견입니다. 사실과는 다를 수 있습니다.

물론 생성 시간까지 고려한다면 조금 더 복잡해진다.

이진 탐색트리를 생성할 때는 O(Mlog(N)), Trie는 O(M*N)만큼의 시간 복잡도를 가지기 때문에 이진 탐색 트리 생성 시에 더 적은 시간을 쓰게 된다.

log(N)과 N의 차이는 매우 크기 때문에 Trie 생성에 걸리는 비효율성이 시간적 장점을 다 뺏어가는게 아닐까 생각했다.

하지만 문자열 탐색을 K번 한다고 가정할 경우 얘기가 달라진다.

문자열 탐색이 K번 일어날 때 Trie는 총 O(M*K), 이진탐색은 O(M*K*log(N))의 시간 복잡도가 필요하다.

log(N)이 1보다 크고 곱 연산을 가지기 때문에 K가 커지면 커질수록 Trie의 시간 효율성이 생성 시의 비효율성을 커버할 수 있을 것이라고 생각했다.

 

Trie는 공간적으로 매우 비효율적인 알고리즘이다.

모든 Node에 자식 노드를 가리키는 포인터를 저장해야 하며 일반적인 구현방법으로는 1개 Node에 문자열을 구성한 문자 개수만큼의 포인터를 저장해야 한다.

이런 단점을 해결하기 위해 Map을 활용하여 필요한 노드만 메모리를 할당하는 방식들을 사용하기도 하지만 어쨌든 메모리는 많이 활용된다.

Trie는 총 O(Node 개수 * 포인터 크기 * Node가 가진 포인터 배열 개수)만큼의 메모리가 필요할 수도 있다.

만약, 1000자리의 문자열이 1000개만 들어온다고 하더라도 100만 개의 노드가 필요하고 포인터 크기가 8byte라고 해도 8MB의 크기가 필요하다. 여기에 모든 문자열이 소문자로만 되어 있다 해도 26개 이므로 26 * 8 = 208MB의 메모리가 필요한 것이다.

 

DP와 마찬가지로 시간을 쓸 것인지, 공간을 쓸 것인지 선택하는 알고리즘이며 문자열 검색을 많이 하지 않는 상황에서는 오히려 비효율성을 가질 수도 있는 알고리즘이라고 할 수 있겠다.

주로 검색어 자동완성, 사전에서 찾기, 문자열 검사 등의 "문자열 비교" 상황이 많이 발생하는 상황에서 많이 활용한다.

---

트라이의 자바

Trie의 Root Node는 비어 있고 첫 번째 자식 노드에 문자열의 첫 문자가 저장된다.

최대한 메모리를 절약하기 위해 Map을 사용해 Trie를 구현해보도록 하자.

 

1. Node 클래스 생성

class Node {
    // Key : 다음 Index 문자, Value : 다음 Index 문자의 자식 Node를 저장할 Node
    Map<Character, Node> childNode = new HashMap<>();
    // 현재 Node가 단어의 끝인지 아닌지 체크
    boolean end;
}

여기에서 꽤 중요한 것이 "boolean end"이다. 예를 들어 "gone, go"로 Trie를 만들 때 "go"가 gone의 중간이자 go라는 문자열과 일치한다는 것을 명시해줘야 한다.

따라서 "o"에 true 값을 넣어줌으로써 "go"라는 문자열이 있음을 명시해 주는 것이다.

 

2. Trie 클래스 생성

class Trie{
	Node root = new Node();
}

이전에 말했듯 root Node는 완전 비어 있다. 따라서 깡통 Node로만 남겨두자.

 

3. Trie 클래스 메서드 구현

◎ 문자열 추가 기능

void insert(String word) {
    Node thisNode = this.root;

    for (int i = 0; i < word.length(); i++) {
        thisNode = thisNode.childNode.computeIfAbsent(word.charAt(i), k -> new Node());
    }

    thisNode.end = true;
}

로직은 간단하다.

먼저 (i+1)번째 for문의 Node Map의 Key 값 중 i번째 문자가 있는지 확인한다.

만약 Map에 존재한다면 i번째 문자가 현재 Node의 Child Node로써 이전에 추가시켜 줬다는 의미이므로 아무런 동작 없이 자식 노드로 이동하고 만약 저장되어 있지 않는다면 i번째 문자를 자식 Node로써 추가해줘야 하므로 "c -> new TrieNode()"로써 Node를 추가한다.

 

왜 (i+1) 번째 문자가 아닌 i번째 문자를 i번째 for문에서 검색하는지 헷갈릴 수 있다.

이는 매우 간단한 이유인데, 바로 Root Node가 비어 있기 때문에 첫 번째 for문은 0번째 문자를 확인하는 단계이므로 이런 상황이 벌어지는 것이다.

 

◎ 문자열 삭제 기능

Trie에 저장한 단어를 삭제하는 과정이다.

만약 코딩 테스트에서만 쓸거면 delete 메서드는 큰 필요는 없다. 하지만 Trie를 실제로도 활용하기 위해선 필요한 메서드이므로 알고 가자.

 

Trie에서 하위 노드는 부모 노드에 대한 정보를 가지고 있지 않기 때문에 먼저 가장 하위 노드로 내려가 삭제 대상 단어를 탐색한 후 다시 올라오며 실제 삭제하는 Callback 형식으로 구현되어야 한다.

 

신경 써야 할 것인 3가지이다.

 

삭제할 첫 노드(가장 하위 노드)는 end = true여야 한다.

만약 end = false라면 없는 단어라는 의미이기 때문에 삭제할 수 없다.(물론 이런 경우는 거의 주어지지 않을 것이다)

 

자식 노드를 가지고 있지 않아야 한다.

이전 단계에서 현재 Node의 자식 중 1개를 삭제했다.

만약 현재 Node가 자식 Node를 가지고 있다는 것은 현재 삭제하려는 단어 이외에도 다른 단어가 현재 Node를 중간 문자로 가지고 있다는 의미이다.

따라서 삭제하면 안 된다.

 

삭제하는 과정 중 end = false여야 한다.

end = true라면 다른 단어의 마지막 문자라는 의미이기 때문에 자식 노드가 없을 수도 있다.

하지만 이 문자를 삭제하면 이 문자를 마지막으로 하는 문자열 또한 삭제되는 것과 같은 효과를 받으므로 삭제하면 안 된다.

public void delete(Node thisNode, String word, int index){
    char character = word.charAt(index);

    // 아예 없는 단어이기 때문에 삭제를 진행할 수 없음
    if(!thisNode.childNode.containsKey(character)) throw new Error("존재하지 않는 단어");

    Node childNode = thisNode.childNode.get(character);
    index++;

    if(index == word.length()){ // 마지막 문자열까지 검색했다.
        // DELETE라는 단어밖에 없는데 DEL을 삭제하려 할 때 발생하는 에러
        if (!childNode.end) throw new Error("존재하지 않는 단어");

        // DEL을 삭제할 때 DELETE라는 단어가 있는 경우도 있으므로 end를 false로 설정해줘야 함
        childNode.end = false;

        // 자식 노드가 자식 노드를 가지고 있지 않음. 
        // 즉 삭제할 단어가 자식 노드의 문자를 가지는 유일한 단어이므로 현재 노드의 자식에서 배제
        if (childNode.childNode.isEmpty()){
            thisNode.childNode.remove(character);
        }
    }
    else{
        // 먼저 마지막 Node까지 이동 하고 Callback 방식으로 실행해야 함
        delete(childNode, word, index);

        // 자식 노드의 자식 노드가 없고 다른 문자열의 마지막 글자가 아니므로 삭제 가능
        if(!childNode.end && childNode.childNode.isEmpty()){
            thisNode.childNode.remove(character);
        }
    }
}

 

검색은 Root Node로부터 자식 노드로 1개씩 이동하면 되기 때문에 따로 구현하지는 않겠다.