(5670) 휴대폰 자판

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

단계별로 풀어보기

46단계(문자열 알고리즘 1) 5번째

 

 

 

트라이 자료 구조를 이용해 자판을 누르는 횟수를 계산하는 문제.

다음 글자가 2개 이상이거나(map의 사이즈가 2 이상), 현재 글자가 단어의 마지막이라면(finish가 true) 현재 글자에서 다음 글자로 가기 위해서는 자판을 한 번 눌러야 한다. 트라이의 기존 find함수를 변형해 이 기능을 구현하면 된다.

또한 첫 번째 글자는 절대 추론하지 않으므로 편의를 위해 사용되지 않는 글자를 하나 넣었다. 첫 글자를 탐색할 때 이 글자로 인해 map의 사이즈는 항상 2 이상이므로 첫 글자를 탐색할 땐 항상 자판을 누르는 것으로 판정된다.

 

 

 

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Trie {
  bool finish= false;
  map<char, Trie*> next;
  ~Trie() { for(auto& iter:next)  delete iter.second; }
  
  void insert(string_view s){
    if(s.empty()) { finish= true;  return; }
    
    if(next[s[0]]==nullptr)  next[s[0]]= new Trie();
    next[s[0]]->insert(s.substr(1));
  }
  
  int find(string_view s){
    if(s.empty())  return 0;
    
    return (next.size()>1|finish) + next[s[0]]->find(s.substr(1));
  }
};

void solve(int n){
  vector<string> v(n);
  Trie* root= new Trie();
  double res= 0.0;
  
  root->insert("!");
  for(int i=0;i<n;i++){
    cin >> v[i];
    root->insert(v[i]);
  }
  
  for(int i=0;i<n;i++){
    res+= root->find(v[i]);
  }
  
  cout << res/n << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  cout << fixed;  
  cout.precision(2);
  
  int n;
  
  while(cin >> n){
    solve(n);
  }
  
  return 0;
}