TopCoder SRM328 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

さまざまな色からなる数珠状のネックレスについて考える。色はアルファベットの大文字1字で表される。すると、ネックレスは以下のような文字列で記述することができる。つまり、ある珠から始め、時計回り、あるいは反時計回りで辿った順序を用いて、現れた色の順序によって文字列が作成されるということである。明らかに同じネックレスは複数の表現方法がある。例えば"CDAB"は"DABC"などと同じになる。さて、necklaceというネックレスを表す1つの文字列が与えられたときに、辞書式順序でもっとも最初に来るneckleceと同じネックレスの表現を返すメソッドを作成せよ。例えば、"CDAB"であれば"ABCD"がもっとも最初に来ることになる。

私の解答はこちら。

import java.util.ArrayList;
import java.util.Collections;

public class MarbleNecklace {

 public String normalize(String necklace) {
  String rep = necklace + necklace;
  ArrayList<String> aList = new ArrayList<String>();
  for( int i=0 ; i<necklace.length() ; i++ ){
   String s = rep.substring(i, i+necklace.length());
   aList.add(s);
   s = rep.substring(rep.length()-i-necklace.length(), rep.length()-i);
   StringBuffer sb = new StringBuffer(s);
   aList.add(sb.reverse().toString());
  }
  Collections.sort(aList);
  return aList.get(0);
 }

}

得点は202.50/250、中央値は約193点。いったん2倍の文字列にし、時計回りと反時計周りを同時にリストに入れ、最後にリストをソートして先頭の要素を取り出せばよい。Collections.sortは、コレクションを自然な順序で並べ替えてくれるので、文字列型のデータが入ったArrayListのソートであれば、辞書式順序で並べ替えてくれることになる。この性質より、先頭のものを取り出せば、答えになる。