[Grind75-LeetCode] Implement Trie (Prefix Tree) JAVA

반응형

728x90

[Grind75-LeetCode] Implement Trie (Prefix Tree) - Medium

---

접근

• Trie

---

풀이

이 문제는 Trie 자료 구조를 통한 삽입, 검색, 접두사 검색을 구현하는 문제이다. 이 문제를 풀기 위해서는 우선 Trie 자료 구조에 대해 알아야 한다. 

 

Trie란 문자열을 검색하고 저장하기 위해 최적화된 트리 기반 구조이다. 단어 집합을 다루는 데 효율적이며, 주로 자동 완성, 접두사 검색, 사전 구현 등에 사용된다. 기본적인 트리 구조를 따르기 때문에 자식 노드와 마지막인지를 나타내는 플래그를 가진다. 기본적으로 한 문자 단위로 쪼개져 저장이 된다. 아래는 Trie에 저장된 모습이다.

Trie 구조

현재 Trie에 apple, app, aproach, ban, banana, call, cash라는 단어들이 저장되어 있다고 가정한 모습이다. 빨간색으로 되어 있는 문자는 종료 플래그를 표시한 것으로 루트 노드에서 시작해 종료 플래그까지의 문자를 합친 것이 하나의 문자열로 볼 수 있다.  그러므로 종료 플래그까지인 app은 Trie에 저장되어 있는 단어이지만 appl은 l이 종료 플래그 표시가 되어 있지 않기 때문에 저장되지 않은 단어인 것이다. 그림을 보면 대충 어떤 구조이고 동작 방식이 어떨지 가늠할 수 있으므로 코드로 넘어가겠다.

 

처음엔 다른 문제를 풀 때처럼 노드에 문자를 저장할 변수와 종료 플래그 그리고 child 리스트를 가진 형태로 풀기 시작했는데 그럴 경우 문자 존재 여부 확인에 너무 많은 시간을 소요하고 좋지 않은 방법인 거 같아 다른 방법을 찾았다. HashMap을 사용해 해당 문자가 존재하는지 확인하는 방법이 더 간편하고 성능이 좋았는데 이번 문제의 경우 알파벳 소문자만 입력만을 보장하기에 26칸의 크기를 가진 배열을 사용해 구현하는 것이 최선의 방법이었다. 

class Node {
    public Node[] child;
    private boolean endFlag;

    public Node() {
        this.child = new Node[26];
        this.endFlag = false;
    }

    public void end() {
        this.endFlag = true;
    }

    public boolean isEnd() {
        return endFlag;
    }
}

Trie에 사용할 노드를 구현한 클래스이다. child 노드를 26칸 배열로 가져 각각 알파벳을 표현한다. 내부 필드를 둘 다 private로 선언하려 했는데 child의 경우 연산이 길어져 public으로 두고 endFlag만 private로 선언하고 메서드를 만들어 줬다. 그냥 public으로 선언하고 메서드가 없어도 무관한 개인 취향이다. 

class Trie {
    private Node trie;

    public Trie() {
        trie = new Node();
    }

    public void insert(String word) {
        Node pointer = trie;

        for (char c : word.toCharArray()) {
            int n = c - 'a';

            if (pointer.child[n] == null) {
                pointer.child[n] = new Node();
            }
            pointer = pointer.child[n];
        }

        pointer.end();
    }

Trie 클래스의 생성자와 insert 메서드로 객체가 생성될 경우 내부 Node 객체를 초기화한다. insert 메서드는 문자열을 저장하기 위한 메서드이다. 반복문 내 child로 pointer를 넘기기 위한 포인터용 객체를 생성하여 trie 객체의 참조값을 할당한다. 그리고 문자열을 한 문자씩 순회하며 Trie에 저장되어 있지 않다면 저장하고 저장되어 있다면 해당 문자로 포인터를 이동한다. 문자열 저장이 끝나면 마지막 문자의 종료 플래그를 true로 변경하여 문자열의 끝을 알린다. 

    public boolean search(String word) {
        Node pointer = trie;

        for (char c : word.toCharArray()) {
            int n = c - 'a';

            if (pointer.child[n] == null) {
                return false;
            }

            pointer = pointer.child[n];
        }

        return pointer.isEnd();
    }

    public boolean startsWith(String prefix) {
        Node pointer = trie;

        for (char c : prefix.toCharArray()) {
            int n = c - 'a';

            if (pointer.child[n] == null) {
                return false;
            }

            pointer = pointer.child[n];
        }
        return true;
    }

다음은 기본 검색과 접두사 검색이다. 기본 검색의 경우 검색하는 문자열이 저장되어 있는지를 확인하는 메서드이고 접두사 검색은 해당 접두사가 저장되어 있는지 확인하는 것으로 종료 플래그를 따지냐 따지지 않느냐의 차이로 내용은 거의 동일하다. Trie를 순회하며 문자가 저장되어 있는지 확인하고 모든 문자가 저장되어 있다면 접두사 검색의 경우 true를 반환하고 기본 search의 경우 종료 플래그가 true인지 확인하고 true라면 해당 문자열이 저장된 것으로 true를 반환한다.  

---

처음 제출을 했을 때 실행 시간 34ms에 Beats78%로 애매한 수치가 나와 다른 코드들을 살펴봤다.

첫 실행 결과

그러나 대부분의 코드가 비슷한 방식으로 구현되어 있었고 Beats가 90%가 넘는다고 하는 코드도 봤지만 동일한 내용이었고 비슷한 성능이 나왔다. 그래서 내 코드를 다시 제출해 봤는데 매번 제출할 때마다 결과가 바뀐다. 테스트케이스로 주어지는 입력들이 계속 달라지는 건가 성능이 아주 들쭉날쭉하다. 

동일한 코드

메모리 사용량도 매번 달라지는걸 봐선 입력으로 주어지는 값이 매번 달라지던가 정해진 입력값 집단 중에서 랜덤으로 테스트되던가 해서 그런 거 같다. 

---

전체 코드

class Trie {
    private Node trie;

    public Trie() {
        trie = new Node();
    }

    public void insert(String word) {
        Node pointer = trie;

        for (char c : word.toCharArray()) {
            int n = c - 'a';

            if (pointer.child[n] == null) {
                pointer.child[n] = new Node();
            }
            pointer = pointer.child[n];
        }

        pointer.end();
    }

    public boolean search(String word) {
        Node pointer = trie;

        for (char c : word.toCharArray()) {
            int n = c - 'a';

            if (pointer.child[n] == null) {
                return false;
            }

            pointer = pointer.child[n];
        }

        return pointer.isEnd();
    }

    public boolean startsWith(String prefix) {
        Node pointer = trie;

        for (char c : prefix.toCharArray()) {
            int n = c - 'a';

            if (pointer.child[n] == null) {
                return false;
            }

            pointer = pointer.child[n];
        }
        return true;
    }
}

class Node {
    public Node[] child;
    private boolean endFlag;

    public Node() {
        this.child = new Node[26];
        this.endFlag = false;
    }

    public void end() {
        this.endFlag = true;
    }

    public boolean isEnd() {
        return endFlag;
    }
}