백준 5670번 : 휴대폰 자판 - Trie C++

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

5670번: 휴대폰 자판

1. 문제설명

휴대폰 자판을 입력할 때 자동완성기능이 존재하면,

특정 단어를 입력하기 위해서 자판을 몇번 눌러야 하는지 계산하는 문제이다.

 

단어 리스트가 주어지고, 각 단어마다 몇번 눌러야하는지 구하는 과정에서

트라이 알고리즘을 이용해야 문제를 시간내에 해결할 수 있다.

 

 

5670 트라이

주어진 단어로 위와 같이 트리를 미리 구현하고

분기점과 단어가 끝나는 지점마다 카운트해주어야

하나의 단어를 입력하기 위해 자판을 몇번 입력해야하는지 알아낼 수 있다.

 

---

 

2. 문제풀이코드 C++

#include <bits/stdc++.h>
#define ALPHABETS 26
using namespace std;


const int ROOT = 1;
int unused = 2;
const int MX = 1000'003;
int nxt[MX][26];
bool chk[MX];
int childs[MX];

int ctoi(char c){
    return c-'a';
}

void insert(string &s){
    int cur = ROOT;
    for(auto c : s){
        if(nxt[cur][ctoi(c)] == -1){
            childs[cur]++;
            nxt[cur][ctoi(c)] = unused++;
        }
        cur = nxt[cur][ctoi(c)];
    }
    chk[cur] = true;
}


int count(string &s){
    int res = 1;

    int cur = ROOT;
    for(int i=0; i<s.length();i++){
        cur = nxt[cur][ctoi(s[i])];

        if(i!=s.length()-1 && (childs[cur] > 1||chk[cur])){
            res++;
        }
    }
    return res;
}


vector<string> words;



int n;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> n){
        words.clear();
        unused = 2;

        fill(childs, childs+MX , 0);
        fill(chk, chk+MX, 0);
        for(int i=0; i<MX; i++){
            fill(nxt[i], nxt[i]+26, -1);
        }

        for(int i=0; i<n; i++){
            string s;
            cin >> s;
            insert(s);
            words.push_back(s);
        }


        double sum = 0;
        for(auto s : words){
//            cout << s << '\n';
//            cout << count(s) << '\n';
            sum += count(s);
        }


        cout << fixed;
        cout.precision(2);
        cout << sum / n << '\n';



    }

    return 0;
}