2012年8月11日土曜日

TopCoder SRM416 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について意訳で説明する。

英語の典型的なテキストについて、いくつかの文字が他の文字よりも頻繁に現れるということが一般的に知られている。例えば、英語の長文においては、約12.31%の文字がeになる。言語学部の友人が、与えられたテキストの中で最も頻繁に現れる文字が知りたいということで、手伝ってくれるよう頼んできた。テキストはtext[]という文字列型の配列で与えられる。このとき、テキストでもっとも頻繁に現れる文字を返すメソッドを作成せよ。もし一番頻繁に現れる文字が複数ある場合、それらをアルファベット順で返すようにせよ。なお、文字列は小文字のアルファベットと空白しかないものとする。

私の解答はこちら。

public class MostCommonLetters {

 public String listMostCommon(String[] text) {
  int[] times = new int[26];
  for( int i=0 ; i<text.length ; i++ ){ // ここで文字の頻度集計
   for( int j=0 ; j<text[i].length() ; j++ ){
    char c = text[i].charAt(j);
    if( c != ' ' ){
     times[c-'a']++;
    }
   }
  }
  int maxTimes = -1;
  for( int i=0 ; i<times.length ; i++ ){ // 最大出現回数を調べる
   maxTimes = Math.max(maxTimes, times[i]);
  }
  String ret = "";
  for( int i=0 ; i<times.length ; i++ ){ // 出現回数が最大となる文字を集める
   if( times[i] == maxTimes ){
    char c = (char)('a'+i);
    ret += c;
   }
  }
  return ret;
 }

}

得点は241.25/250、1回のsubmitでシステムテストクリア。中央値は約186点。素直な集計の問題です。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計