ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 0242 Input Candidates

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0242


・概要
携帯電話のメールなどでよく使う文字列の入力候補を表示させるような問題です。
問題が日本語なのであとは省略。


・解法
実装問題です。
まず与えられた文字列をマップに保存させ、出現頻度を数えておきます。
次に調べたいアルファベットと先ほど保存したマップの中身を比較していき、頭文字が同じ単語をvectorに保存させます。
最後に先ほど保存したvectorを出現頻度順にソートさせ、出力させればよいです。
(もっと効率のよい方法があると思います。)


ソースコード

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

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)
#define f first
#define s second
#define pb push_back

struct Data{
   string word;
   int count;

   bool operator < (Data d) const{
      if(count==d.count)return word < d.word;
      else return count > d.count;
   }
};

map<string, int> table;
vector<Data> data;

void convert(string s){
   string tmp = "";
   rep(i,s.size()){
      if(isspace(s[i])){
	 table[tmp]++;
	 tmp="";
      }
      else{
	 tmp += s[i];
      }
   }
   table[tmp]++;
}

void solve(char key){
   for(map<string,int>::iterator it = table.begin() ; it != table.end() ; it++){
      string word = (*it).f;
      int count = (*it).s;
      if(word[0]==key){
	 Data tmp;
	 tmp.word = word;
	 tmp.count = count;
	 data.pb(tmp);
      }
   }

   sort(data.begin(), data.end());
   
   if(data.size()==0)cout << "NA" << endl;
   else{
      for(int i = 0 ; i < min(5, (int)data.size()) ; i++){
	 if(i==0)cout << data[i].word;
	 else cout << " " << data[i].word;
      }
      cout << endl;
   }
}

int main(){
   int n;
   while(cin >> n){
      if(n==0)break;

      cin.ignore();
      data.clear();
      table.clear();
      
      rep(i,n){
	 string s;
	 getline(cin,s);
	 convert(s);
      }
      
      char key;
      cin >> key;
      solve(key);
   }
   return 0;
}