TopCoder SRM357 Div2 250Pts

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

数学のテストにおいて、上手いニーモニックフレーズを持つことはしばしば役に立つ。例えば25735という数字は"is there anybody out there"と記憶することができる。もし、すべての単語の文字数を数えることができれば、25735という元の数字を得ることができる。不幸なことに、教授は学生にでたらめな数字を記憶させ、テストをするのを好んでいる。そのシステムを負かすため、あなたは覚えなければならない数字を表すニーモニックフレーズを見つける計画をしている。numberという数字を文字列とdictionary[]という文字列型の配列が与えられたとき、単語をスペース1文字で区切ったリストを返せ。ここで、各単語はdictionaryの要素であり、どの単語も1度しか利用しない。フレーズはnumberの桁数と同じである。i番目の単語の長さはi番目の数字に一致する。もし複数のフレーズが回答の候補にある場合(訳注：例えば同じ223のように同じ数字が複数回登場した場合を考えよ)は、アルファベット順で最初に来るものを返すようにせよ。

例えばnumber="1234"、dictionary[]={"This","is","a","pen"}であれば、"a is pen this"になる。

私の解答はこちら。

import java.util.Arrays;

public class MnemonicMemory {

 public String getPhrase(String number, String[] dictionary) {
  Arrays.sort(dictionary); // 単語の長さごとにアルファベット順でソート
  StringBuilder sb = new StringBuilder();
  boolean[] isUsed = new boolean[dictionary.length]; // 使用済みの単語の位置にtrueを入れる
  for( int i=0 ; i<number.length() ; i++ ){
   int n = number.charAt(i) - '0'; // 文字数を解釈
   for( int j=0 ; j<dictionary.length ; j++ ){
    // 未使用の単語が登場して、文字数が条件に合う
    if( dictionary[j].length() == n && isUsed[j] == false ){
     isUsed[j] = true;
     sb.append(dictionary[j]);
     sb.append(" ");
     break;
    }
   }
  }
  return sb.toString().trim(); // 最後の空白を削るためtrim()する
 }

}

得点は218.56/250、中央値は約187点。最初にソートしておくことで、文字数が一致した物のうち、先頭に出てきた未使用の単語を利用すればよいということにできるのがポイント。