본문으로 바로가기

[프로그래머스] (Trie) 자동완성 (C++ / 2018 KAKAO BLIND 3차)

category Algorithms/Trie 2021. 8. 3. 11:17

자동완성 (Level 4)

문제

전체 문제 보기

 

코딩테스트 연습 - [3차] 자동완성

자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g

programmers.co.kr

트라이 자료구조

카카오는 해설에서 이 문제를 트라이를 사용하는 풀이와 정렬을 활용하여 풀 수 있다고 설명했다. 필자는 트라이를 이용하여 문제를 풀어보았다. 트라이는 접두사를 검색하거나 단어 자체를 검색하는데 특화된 문자열 집합 자료구조이다. 때문에 검색엔진에서도 많이 활용되는 자료구조라고 한다. 아래의 그림은 "abc", "go", "gone", "word", "world"를 저장한 트라이 자료구조이다.

트라이의 각 노드는 최대 문자열에 입력될 수 있는 문자의 개수만큼의 자식을 가질 수 있다. 만약 문자열이 숫자로만 이루어져 있다면 10개의 자식을 가질 수 있고, 알파벳 소문자로만 이루어졌다면 최대 26개의 자식을 가질 수 있다. 따라서 트라이의 각 노드는 자식 노드를 가리키는 배열 혹은 해시 테이블을 가진다. (배열을 활용하는 경우에도 해시 함수의 역할을 하는 GetIndex함수가 필요하기 때문에 개념적으로는 해시테이블과 동일하다.) 그리고 일반적으로 각 노드는 isEnd라는 boolean 타입의 변수를 가지고 현재 노드가 문자열의 끝인 경우 true를 반환한다.

 

탐색에 특화된 자료구조는 이진 검색트리가 있다. 이진 탐색 트리는 검색을 \(O( \mbox{log} n)\)만에 이루어지게 하는 효율적인 자료구조이다. 하지만 트리에 저장할 데이터가 문자열이라면 문자 하나씩 비교해야 하기 때문에 문자열 길이가 \(l\)일 경우 \(O(l\mbox{log}n)\) 만큼의 시간이 필요하다. 하지만 트라이를 활용할 경우 \(O(l)\) 회 만에 연산을 끝낼 수 있다는 장점이 있다.

 

일반적인 트라이의 노드 구성은 다음과 같다.

struct Node {
    Node() : isEnd(false)
    {
    }
    unordered_map<char,Node*> links;
    bool isEnd;
};

만약 배열을 사용한다면 다음과 같이 활용할 수 도 있다. (GetIndex 함수를 해시함수로 이해한다면 배열을 활용해서 직접 간단한 해시테이블을 구성한 것으로 볼 수 있다.) 가독성면이나 활용 면에서는 인덱싱 과정이 자체 내장된 해시 테이블이 우세해 보인다. 반면 인덱싱 연산이 간단하기 때문에 성능면에서는 배열이 더 우세해 보인다. 또한 배열을 사용하게 될 경우 모든 노드는 항상 26개의 자식노드 포인터를 가진다. 반면 해시테이블을 사용할 경우 동적 버킷이 추가되기 때문에 공간활용도에서 우세하다. 아래에서 두 가지를 모두 구현하여서 성능 차이도 비교해보겠다.

struct Node {
    Node() : isEnd(false)
    {
    }
    array<Node*, 26> links;
    bool isEnd;
    static::size_t GetIndex(char ch) { return static_cast<size_t>(ch - 'a'); }
};

문제 풀이

문제를 풀면서 트라이를 더 살펴보자. 우선 이번 문제에서는 여러 문자열들이 학습되었을 때 단어를 찾을 때 입력해야 할 총 문자 수를 리턴해야한다. 그림 1을 살펴보자. 만약 우리가 wor까지 입력했다면 이 단어가 word 인지 world인지 알 수 없다. 왜냐하면 wor은 word가 될 수도 있고 world가 될 수도 있기 때문이다. 즉 'w', 'o', 'r' 노드는 두 개의 문자열이 참조하고 있는 노드이다. 이 문제에서는 각 노드에 isEnd boolean 변수는 사용할 일이 없어 보인다. 대신 각 노드가 몇개의 문자열에서 참조되고 있는지 참조 카운터를 기록하는 것이 필요해 보인다. 따라서 트라이의 노드를 다음과 같이 사용하자. 가독성을 위해 해시 테이블을 활용한 구현을 먼저 다루겠다.

struct Node {
    Node() : links{}, referenceCount(0)
    {}
    unordered_map<char,Node*> links;
    int referenceCount;
};

다음으로 트라이 클래스에는 다음과 같은 기능 드 다음과 같이 선언하자.

class Trie {
public:
    Trie();
    ~Trie();
    void Insert(const string& word);       // 트라이에 문자열 추가 함수 
    int AutoComplate(const string& word);  // 해당 문자열을 찾기위해 필요한 입력 수를 반환
private:
    Node* root;        // 루트 노드
    void recurDelete(Node* node);    // ~Trie()에서 사용할 재귀함수.
};

트라이 클래스의 활용은 다음과 같이 할 수 있다.

int solution(vector<string> words) {
    int answer = 0;
    Trie trie;
    for (const string& word : words)
    {
        trie.Insert(word);
    }

    for (const string& word : words)
    {
        answer += trie.AutoComplate(word);
    }
    return answer;
}

트라이 자료구조에 문자열을 삽입하는 Trie::Insert 함수에서는 문자열의 0번째 문자부터 마지막 문자까지 반복하며 저장할 위치를 찾고, 해당 노드의 referenceCount를 1 증가시킨다. 삽입 연산에서는 문자열 길이가 \(l\)이라면 \(O(l)\)만큼의 연산이 필요하다.

void Trie::Insert(const string& word)
{
    Node* cur {root};
    for(size_t i {0}; i < word.length(); ++i)
    {
        // i번째 문자를 저장할 노드 탐색      
        if(cur->links.find(word[i]) == cur->links.end())
        {
            cur->links[word[i]] = new Node();
        }
        Node* nextNode {cur->links[word[i]]};
        
        // nextNode의 참조를 1 증가 시킨다.
        nextNode->referenceCount++;
        cur = nextNode;
    }
}

모든 문자열을 저장하면 다음과 같을 것이다.

다음으로 자동완성기능을 위해서 최소로 입력해야 할 문자 수를 계산하는 AutoComplate함수를 구현해보자. 문자열을 하나씩 탐색할 때마다 트라이의 깊이 값을 1 증가시키기 위해 depth 변수를 사용한다. 그리고 참조가 1인 노드는 이제 문자열을 완성할 수 있다. 때문에 참조가 1이 될 때까지 탐색을 진행하자. 만약 "go"와 같은 경우에는 문자열 길이 끝까지 탐색해도 참조는 2이다. 그래서 문자열 길이가 반환될 것이다. AutoComplate함수 또한 문자열 길이가 \(l\)이라면 \(O(l)\)만큼의 연산이 필요하다.

int Trie::AutoComplate(const string& word)
{
    Node* cur {root};
    int depth {0};
    for(size_t i {0}; i < word.length(); ++i)
    {
        // 참조가 1인 노드는 문자열을 완성 할 수 있다.
        if(cur->referenceCount == 1)
            break;

        size_t idx = Node::GetIndex(word[i]);
        Node* nextNode {cur->links[idx]};
        cur = nextNode;
        depth++;
    }
    return depth;
}

성능

앞서 언급한 대로 Trie::Insert 함수와 Trie::AutoComplate 함수 모두 문자열 길이 \(l\)에 대해서 \(O(l)\)만큼의 연산이 요구된다. 모든 문자열이 두 함수를 한번씩 호출해야 하기 때문에 전체 시간 복잡도는 문자열 개수 \(n\)에 대해서 \(O(l\cdot n)\)이다. 그리고 공간 복잡도는 문자 하나당 노드 하나가 필요하기 때문에 마찬가지로 \(O(l\cdot n)\)이 된다.

 

앞서 언급한 해시를 사용했을 때와 배열을 사용했을 때 시간복잡도는 동일하다. 하지만 배열을 사용할 경우 간단한 인덱싱 연산을 사용할 수 있는 반면 std::unordered_map을 사용할 경우 안정성을 위해 더 복잡한 해시함수를 사용하기 때문에 속도 차이가 발생한다. 다음은 해시 맵을 사용했을 때와 배열을 사용했을 때의 시간 차이를 비교한 사진이다. 해시맵을 배열로 수정하면 전체 성능이 약 1.8배 정도 좋아짐을 확인할 수 있다.

 

반면 메모리 사용량에서는 동적으로 공간을 활용하는 해시맵이 더 성능이 좋음을 확인할 수 있다. 시간과 공간에 트레이드오프가 있기 때문에 상황에 맞게 골라서 사용하자.

▲ 해시맵(좌)과 배열(우)의 성능 비교

전체 코드

동적할당한 노드를 삭제하는 소멸자 코드는 재귀 함수를 활용하여 구현하였다. Solution함수에서 정적 변수로 Trie를 선언하였기 때문에 Solution 함수가 종료될 때 트라이의 소멸자 함수가 호출된다.

 

▼ 배열을 활용한 구현

#include <string>
#include <vector>
#include <array>
using namespace std;

struct Node {
    Node() : links{}, referenceCount(0)
    {}
    array<Node*, 26> links;
    int referenceCount;
    static::size_t GetIndex(char ch) { return static_cast<size_t>(ch - 'a'); }
};

class Trie {
public:
    Trie();
    ~Trie();
    void Insert(const string& word);       // 트라이에 문자열 추가 함수 
    int AutoComplate(const string& word);  // 해당 문자열을 찾기위해 필요한 입력 수를 반환
private:
    Node* root;        // 루트 노드
    void recurDelete(Node* node);    // ~Trie()에서 사용할 재귀함수.
};

Trie::Trie() {
    root = new Node();
}
Trie::~Trie() {
    recurDelete(root);
}
void Trie::Insert(const string& word)
{
    Node* cur {root};
    for(size_t i {0}; i < word.length(); ++i)
    {
        // i번째 문자를 저장할 노드(nextNode) 인덱스 계산       
        size_t idx = Node::GetIndex(word[i]);
        if(cur->links[idx] == nullptr)
        {
            cur->links[idx] = new Node();
        }
        Node* nextNode {cur->links[idx]};

        // nextNode의 참조를 1 증가 시킨다.
        nextNode->referenceCount++;
        cur = nextNode;
    }
}
int Trie::AutoComplate(const string& word)
{
    Node* cur {root};
    int depth {0};
    for(size_t i {0}; i < word.length(); ++i)
    {
        // 참조가 1인 노드는 문자열을 완성 할 수 있다.
        if(cur->referenceCount == 1)
            break;

        size_t idx = Node::GetIndex(word[i]);
        Node* nextNode {cur->links[idx]};
        cur = nextNode;
        depth++;
    }
    return depth;
}
void Trie::recurDelete(Node* node)
{
    for (Node* node : node->links)
    {
        if (node != nullptr)
        {
            recurDelete(node);
        }
    }
    delete node;
}

int solution(vector<string> words) {
    int answer = 0;
    Trie trie;
    for (const string& word : words)
    {
        trie.Insert(word);
    }

    for (const string& word : words)
    {
        answer += trie.AutoComplate(word);
    }
    return answer;
}

▼ 해시맵을 활용한 구현

#include <string>
#include <vector>
#include <array>
#include <unordered_map>
using namespace std;

struct Node {
    Node() : links{}, referenceCount(0)
    {}
    unordered_map<char,Node*> links;
    int referenceCount;
};

class Trie {
public:
    Trie();
    ~Trie();
    void Insert(const string& word);       // 트라이에 문자열 추가 함수 
    int AutoComplate(const string& word);  // 해당 문자열을 찾기위해 필요한 입력 수를 반환
private:
    Node* root;        // 루트 노드
    void recurDelete(Node* node);    // ~Trie()에서 사용할 재귀함수.
};

Trie::Trie() {
    root = new Node();
}
Trie::~Trie() {
    recurDelete(root);
}
void Trie::Insert(const string& word)
{
    Node* cur {root};
    for(size_t i {0}; i < word.length(); ++i)
    {
        // i번째 문자를 저장할 노드 탐색      
        if(cur->links.find(word[i]) == cur->links.end())
        {
            cur->links[word[i]] = new Node();
        }
        Node* nextNode {cur->links[word[i]]};

        // nextNode의 참조를 1 증가 시킨다.
        nextNode->referenceCount++;
        cur = nextNode;
    }
}
int Trie::AutoComplate(const string& word)
{
    Node* cur {root};
    int depth {0};
    for(size_t i {0}; i < word.length(); ++i)
    {
        // 참조가 1인 노드는 문자열을 완성 할 수 있다.
        if(cur->referenceCount == 1)
            break;

        Node* nextNode {cur->links[word[i]]};
        cur = nextNode;
        depth++;
    }
    return depth;
}
void Trie::recurDelete(Node* node)
{
    for (auto node : node->links)
    {
        if (node.second != nullptr)
        {
            recurDelete(node.second);
        }
    }
    delete node;
}

int solution(vector<string> words) {
    int answer = 0;
    Trie trie;
    for (const string& word : words)
    {
        trie.Insert(word);
    }

    for (const string& word : words)
    {
        answer += trie.AutoComplate(word);
    }
    return answer;
}
댓글 , 엮인글
코딩 레시피
블로그 이미지 dev-sbee 님의 블로그
MENU
CATEGORY
VISITOR 오늘 / 전체

티스토리툴바