TopCoder SRM424 Div2 250Pts

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

古代の呪文を含んだspellという文字列が与えられる。その呪文は暗号化されているいるが、暗号はかなり単純なものである。呪文を解読するために、AとZという文字をすべて見つける必要がある。そして、その順序を判断させるのである。例えば、暗号化された文字列が、"AABZCADZA"であれば、AとZを見つけ出し、それらの順序(A->A->Z->A->Z->A)を反転させて、"AZBACZDAA"という解読結果を得る(AとZの位置だけに注目すると反転していることが分かる)。与えられたspellという文字列に対し、解読した結果得られる文字列を返すようなメソッドを作成せよ。

私の解答はこちら。

import java.util.ArrayList;

public class MagicSpell {

 public String fixTheSpell(String spell) {
  // 出現した文字と出現した位置を記録しておく
  ArrayList<Character> list = new ArrayList<Character>();
  ArrayList<Integer> pos = new ArrayList<Integer>();
  for( int i=0 ; i<spell.length() ; i++ ){
   char c = spell.charAt(i);
   if( c == 'A' || c == 'Z' ){
    list.add(0, c); // 0の位置にcを入れることでAとZの出現順序を反転させている
    pos.add(i);
   }
  }
  StringBuilder sb = new StringBuilder();
  int idx = 0;
  for( int i=0 ; i<spell.length() ; i++ ){
   if( idx == pos.size() ){ // 全部AとZが出てきたら終了
    sb.append(spell.substring(i));
    break;
   }
   if( pos.get(idx) == i ){
    sb.append(list.get(idx));
    idx++;
   }else{
    sb.append(spell.charAt(i));
   }
  }
  return sb.toString();
 }

}

得点は150.26/250、3回目のsubmitでシステムテストクリア。中央値は約229点。idxが最後まで来た時にbreakで終了するように仕向けないと、pos.get(idx)の評価でエラーを起こすことに気付かず嵌る。