[백준 5670] 휴대폰 자판

문제 풀이

 

정리해보면, 사전이 주어졌을 때 각 단어를 입력하기 위해 버튼을 눌러야 하는 최소의 횟수를 구해서 평균을 매기면 된다.

어떻게 하면 최소의 횟수를 구할 수 있을까?

 

사전에 아래와 같이 등록되었다고 생각해보자.

hello

hell

heaven

 

문제에서 보았듯이 첫 글자는 무조건 버튼을 눌러야 한다.

h를 눌러보자.

h를 눌렀더니 자동적으로 e가 타이핑이 된다.

왜냐하면 사전에는 h 다음으로 등록되어 있는 것이 e가 공통이기 때문이다.

그런데 he에서 보자.

he는 hello, hell, heaven 다 될 수 있기 때문에 자동적으로 등록되지 못한다. (선택 장애)

따라서 사용자는 어쩔 수 없이 버튼을 눌러야 한다.

만약에 l을 누른다고 해보자.

l을 누르자마자 자동적으로 l이 추가되어 hell가 된다.

왜냐하면 사전에는 l 다음으로 등록되어 있는 것이 l이 공통이기 때문이다.

 

hell를 만든다고 했다면 총 2번의 버튼 입력이 필요하고,

더 나아가서 hello를 만든다고 한다면 사용자는 버튼을 한 번 더 눌러서 hello를 완성시킨다.

 

버튼의 증가 타이밍을 정리하면 다음과 같다.

1. 첫 글자면 증가
2. 한 노드의 자식 노드 개수가 2개 이상일 때
3. end를 지나칠 때 (hell에서 끝났다는 표시가 있는데 더 나아가서 hello를 만들려고 할 때)

트라이 자료구조에 한 노드의 자식 노드 개수를 파악할 수 있도록 변수를 추가하여 구현한다.

시간 복잡도는 O(100,000(testCase) x 80(문자열 길이)) = O(8,000,000) 이는 1초 이내로 해결할 수 있게 된다.

소스 코드

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int n, ans;
bool init;

struct Trie
{
    Trie* ch[26];
    bool end;
    int cnt;
    
    Trie() : end(false), cnt(0)
    {
        for(int i = 0; i < 26; i++)
            ch[i] = nullptr;
    }
    
    ~Trie()
    {
        for(int i = 0; i < 26; i++)
            if(ch[i]) delete ch[i];
    }
    
    void insert(const char* s)
    {
        if(!*s)
        {
            end = true;
            return;
        }
        
        int cur = *s - 'a';
        if(ch[cur] == nullptr)
        {
            ch[cur] = new Trie();
            cnt++;
        }
        ch[cur]->insert(s + 1);
    }
    
    void find(const char* s)
    {
        if(!*s) return;
        if(init)
        {
            init = false;
            ans++;
        }
        //문자열의 끝을 지날 때도 카운팅
        else if(end) ans++;
        //한 노드의 자식의 노드가 2개 이상일 때 카운팅(분별할 수 없으니까 사용자가 입력해야 된다.)
        else if(cnt >= 2) ans++;
        
        int cur = *s - 'a';
        ch[cur]->find(s + 1);
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cout << fixed;
    cout.precision(2);
    while(true)
    {
        cin >> n;
        if(cin.eof() == true) break;
        
        vector<string> list(n);
        Trie* root = new Trie();
        for(int i = 0; i < n; i++)
        {
            cin >> list[i];
            root->insert(list[i].c_str());
        }
        
        ans = 0;
        for(int i = 0; i < n; i++)
        {
            init = true; //첫글자는 반드시 카운팅!
            root->find(list[i].c_str());
        }
        cout << ans / static_cast<double>(n) << '\n';
        delete root;
    }
    return 0;
}