[BOJ알고리즘, C++]#5670_휴대폰 자판, Trie 자료구조, 트리

 

#1. 문제

https://www.acmicpc.net/problem/5670

 

---

 

#2. 풀이

 

1. Trie 자료구조

[자료구조]#8_Trie 검색 트리

Trie 자료구조는 검색 트리의 한 종류로 각 노드는 문자열의 특정 문자를 나타내며, 자식 노드에 대한 링크와 마지막 문자 여부를 갖습니다.

 

2. 부동 소수점

[BOJ알고리즘, C++]#1008_A/B, C++ 부동 소수점, precision(), fixed

precision을 통해 실수의 전체 자릿수를 n개로 결정하고, fixed를 통해 해당 자릿수를 소수점 아래로 설정해 줍니다.

 

3. 자식 노드가 1개면 자동 입력 기능 활성화, 2개 이상 이면 자동 입력 기능 비 활성화!

1. 먼저, Trie 자료구조의 노드를 구조체로 선언합니다. 구조체 멤버는 '마지막 문자 여부'와 um 컨테이너 형식의 자식 노드에 대한 링크입니다.
2. 다음으로, 입력받은 문자열을 통해 Trie 자료구조를 구성합니다.
3. 입력 받은 문자열을 차례대로 순회하며, Trie 자료구조에서 각 문자열의 각 문자에 대하여 자식 노드 개수를 세고, 유일하다면 넘어가고, 2개 이상이라면 입력을 기다리는 작업으로 카운트를 해줍니다.

 

---

 

#3. 코드

/*
    @문제: 특정 단어를 완성하기 위해 필요한 사용자의 버튼 입력 횟수
    @설명
        1. 첫 단어(루트 노드)는 자동 입력 기능 비 활성화
        2. 현재까지 완성된 문자열 뒤에 오는 문자가 '유일할' 경우(자식 노드가 유일하다) 자동 입력 기능 활성화.
        3. 결론, 첫 단어를 제외한 나머지 글자 중에서 자식 노드가 하나 일 경우, 자동 입력 ON, 반대로 자식 노드가 두 개 이상일 경우, 자동 입력 Off
            -> 중요: hello와 hell 에서, hello 완성을 위해 마지막 l뒤에 'nullptr'도 '자식노드'로 카운트해야 한다. 
        4. 시간 초과 발생! 첫 번째 문자는 이미 count 된 것으로 시작하자!
*/

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

int N;

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

struct Trie
{
private:
    Node* root;

public:
    // 생성자
    Trie(){
        root = new Node();
    }

    // 삽입
    void Insert(string str)
    {
        Node* node = root;
        // #1. 루트 노드부터 차례대로 내려가며, 없다면 추가/있다면 진행
        for(auto c : str)
        {
            if(!node->children.count(c))
            {
                node->children[c] = new Node();
            }
            node = node->children[c];
        }
        // #2. 단말 노드 여부
        node->isTerminal = true;
    }

    // 자동 완성: 첫 번째 문자, 두 개 이상의 자식, 부모 노드의 Terminal 여부
    double autoComplete(string str)
    {
        Node* node = root->children[str[0]];
        double count = 1;
        for(int i=1; i<str.length(); ++i)
        {
            char c = str[i];
            if(node->children.count(c))
            {
                // #1. 자동 완성 비활성화 : 첫 번째 문자, 두 개 이상의 자식, node가 terminal
                if(node->isTerminal == true || node->children.size() > 1)
                    count++;
                node = node->children[c];
            }
            else return count;
        }
        return count;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 고정 소수점 방식 : 소수점 아래 2자리로 고정
    cout.precision(2);
    cout << fixed;

    while(cin >> N)
    {
        Trie* trie = new Trie();
        vector<string> v(N);
        for(int i=0; i<N; ++i)
        {
            cin >> v[i];

            // 트라이 자료구조 구성
            trie->Insert(v[i]);
        }
        // 결과 값 출력
        double res = 0;
        for(int i=0; i<(int)v.size(); ++i)
        {
            res +=trie->autoComplete(v[i]);
        }
        cout << res/(double)v.size() << '\n';   
        delete trie;
    }

    return 0;
}

 

---