[코드트리 챌린지] 4주차

---

 

실력진단 결과

코드트리 4주차 실력진단 결과

---

오늘의 학습

Trie & 트라이

6개의 문자열 "app", "apple", "apply", "apart", "ban", "banana"이 주어졌다고 생각해봅시다. 여기서 "ap"로 시작하는 서로 다른 문자열의 수를 구하기 위해서는 각 문자열과 일일이 비교를 해봐야 할 것입니다.

public class Main {
    // 변수 선언
    public static int n = 6;
    // 주어진 문자열
    public static String[] words = new String[]{
        "app", "apple", "apply", "apart", "ban", "banana"
    };
    // 찾고자 하는 문자열 (prefix)
    public static String target = "ap";

    public static void main(String[] args) {
        // 찾고자 하는 문자열의 길이
        int m = target.length();

        int cnt = 0;
        for(int i = 0; i < n; i++) {
            // prefix가 target과 일치하는 경우라면
            // 수를 세어줍니다.
            if (words[i].substring(0, m).equals(target))
                cnt++;
        }

        System.out.println(cnt);
    }
}

만약 주어진 문자열의 개수를 n, 비교할 문자열의 길이를 m이라 한다면 각 문자열에 대해 비교 문자열의 길이만큼 순회하며 정확히 일치하는지를 판단해야 하므로 위 방법의 시간복잡도는 O(NM)이 될 것입니다.

이때 Trie라는 자료구조를 사용하면 특정 문자열로 시작하는, 즉 특정 문자열을 접두사(prefix)로 하는 서로 다른 문자열의 수를 특정 문자열의 길이에 해당하는 O(M)만에 구할 수 있습니다.

Trie는 주어진 문자열들을 트리 형태로 나타낸 자료구조입니다. 예로 "app", "apple", "apply", "apart", "ban", "banana" 문자열들로 나타낸 Trie의 모습은 아래와 같습니다.

Trie는 Root에서 시작합니다. 각 문자열에 대해 루트에서 시작하여 문자열 내 문자 순서대로 각 문자를 간선으로 하여 트리를 만들어 나갑니다. 만약 "app"을 먼저 Trie에 추가하게 되면 다음 그림이 만들어집니다.

맨 끝 노드에 색칠을 해주는 이유는 해당 노드가 특정 문자열의 맨 끝임을 표시하기 위함입니다. 이는 다양한 문제를 해결하는 데 있어 큰 도움이 됩니다.

그 다음 "apple"이라는 문자열을 Trie에 추가하게 되면 다음과 같이 a, p, p는 같은 노드를 사용하게 되고, l, e에 해당하는 새로운 노드가 생겨나게 됩니다.

이런 방식으로 "app", "apple", "apply", "apart", "ban", "banana" 문자열들을 순서대로 Trie에 추가하여 구성하는 과정은 아래와 같습니다.

 

Trie를 만들기 위해서는 모든 문자열 내 문자를 한번씩만 순회하면 됩니다. 즉, 모든 문자열 길이의 합을 L이라 했을 때 시간복잡도는 O(L)이 됩니다.

이렇게 Trie를 만들어주는 코드는 아래와 같습니다. TrieNode라는 새로운 class를 만들어 각 노드마다 자식들을 26개 관리하고 (소문자 'a'부터 소문자 'z'까지 순서대로 0~25까지의 인덱스로 관리), 문자열의 끝임을 표시해주기 위해 is_end라는 값을 설정해줍니다.

// Trie에 사용되는 노드를 정의합니다.
class TrieNode {
    // 각 노드에는 'a'부터 'z'까지의 문자에 대응되는 26개의 노드 정보가 관리됩니다.
    TrieNode[] children = new TrieNode[26];
    // 해당 노드를 기점으로 하나의 단어가 완성되는지를 판단합니다.
    boolean isEnd;

    // 생성자입니다.
    TrieNode() {
        // 단어 완성에 대한 초기값은 false입니다.
        isEnd = false;

        // 각 문자에 대응되는 노드 정보는 처음에 null이 됩니다.
        for(int i = 0; i < 26; i++)
            children[i] = null;
    }
};

public class Main {
    // 변수 선언
    public static int n = 6;
    public static String[] words = new String[]{
        "app", "apple", "apply", "apart", "ban", "banana"
    };
    
    // 루트 노드에 해당하는 TrieNode를 처음 만들어줍니다.
    public static TrieNode root = new TrieNode();
    
    // 단어 s를 Trie에 넣어줍니다.
    public static void insertWord(String s) {
        // root에서 시작합니다.
        TrieNode t = root;
        for(int i = 0; i < s.length(); i++) {
            // 문자 순서대로 따라가면 됩니다.
            // 'a'부터 'z'까지 사용되므로
            // 각각을 0부터 25까지의 index로 매핑시켜줍니다.
            int index = s.charAt(i) - 'a';
            // 해당하는 노드가 아직 없다면 새로운 노드를 만들어줍니다.
            if(t.children[index] == null)
                t.children[index] = new TrieNode();
            
            // index에 해당하는 노드로 옮겨갑니다.
            t = t.children[index];
        }
        // 최종 위치에 단어의 끝임을 표시해줍니다.
        t.isEnd = true;
    }

    public static void main(String[] args) {
        // Trie에 단어들을 넣어줍니다.
        for(int i = 0; i < n; i++)
            insertWord(words[i]);
    }
}

---

Trie & 트라이 탐색

이렇게 Trie를 만들게 되면 어떻게 "ap"로 시작하는 서로 다른 문자열의 수를 빠르게 구할 수 있게 될까요?

이제 Trie에서 "ap"라는 키워드로 검색을 진행해보겠습니다. 비교할 문자열의 길이를 m(여기서는 "ap"의 길이인 2)이라 했을 때 Trie에서 "ap"를 따라가는데 걸리는 시간은 O(M) 입니다.

이제 O(M)에 위와 같이 ap의 위치를 찾았습니다. 그러면 "ap"로 시작하는 서로 다른 문자열의 수는 이제 "ap"에 해당하는 노드의 자손들 중 빨간색으로 색칠된 노드의 개수가 됩니다. 그 이유는 Trie는 prefix에 대한 tree이며 색칠된 노드는 문자열의 끝을 나타내기 때문입니다.

각 노드마다 자손들 중 빨간색으로 색칠된 노드의 수는 트리 노드의 수가 O(L)이기에 미리 Tree에서 DP를 적용하여 전처리로 값을 O(L)에 구해놓을 수 있습니다. 아직 Tree DP 유형에 대해 잘 모르신다면 해당 유형을 공부하신 후 이 내용을 다시 읽는 것을 추천드립니다.

따라서 Trie를 구성하면 이후 특정 문자열을 접두사로 하는 문제를 효율적으로 해결할 수 있게 됩니다.