휴대폰 자판

백준 5670번: 휴대폰 자판

아이디어

자동완성이 안되는 경우는 단어가 완성되는 경우, 혹은 자식이 2개 이상인 경우이다.
모든 단어가 같은 알파벳으로 시작하더라도 처음에는 버튼을 한 번 눌러줘야 한다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Trie {
    Trie* t[26];
    int cnt;
    bool end;

    Trie() {
        memset(t, 0, sizeof(t));
        cnt = 0;
        end = false;
    }

    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (t[i]) delete t[i];
        }
    }

    void insert(string& s, int idx) {
        if (idx == s.length()) {
            end = true;
            return;
        }
        if (!t[s[idx]-'a']) {
            t[s[idx]-'a'] = new Trie();
            cnt++;
        }
        t[s[idx]-'a']->insert(s, idx+1);
    }

    int solve(string& s, int idx) {
        if (idx == s.length()) return 0;
        if (end || cnt > 1)  return t[s[idx]-'a']->solve(s, idx+1) + 1;
        else return t[s[idx]-'a']->solve(s, idx+1);
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(2);

    int n;
    while (cin >> n) {
        Trie root;
        vector<string> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            root.insert(v[i], 0);
        }
        double ans = 0;
        if (root.cnt == 1) ans += n;
        for (string& s : v) {
            ans += root.solve(s, 0);
        }
        cout << ans/n << '\n';
    }

    return 0;
}

여담

다들 C-style 문자열(const char*)로 trie를 구현하고, 그걸 돌려쓰길래 맘에 안들어서 문자열 레퍼런스랑 인덱스를 넘기는 방식으로 구현했다.