TopCoder SRM366 Div2 250Pts

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

あなたはギターを大量に所持しており、ギターはそれぞれ異なったシリアルナンバーを持っている。シリアルナンバーを高速に検索できるようにしたいので、ソートすることにした。各シリアルナンバーはA-Z、0-9の文字のみからなる。シリアルナンバーAがシリアルナンバーBより前にくるか確認するのは次のステップを踏む。

• AとBが違う長さであれば、短い方が先に来る。
  
• AとBの文字列の長さが同じになる場合、AとBに現れる数字の各桁の総和が小さい方が先に来る。A-Zの数字は0扱い。
  
• それでもAとBに違いがでない場合はアルファベット順になるようにする。
  

serialNumbers[]という文字列型配列が与えられたとき、上のルールに従い文字列型配列を昇順に並び替えたものを返せ。

私の解答はこちら。

import java.util.Arrays;

public class SerialNumbers {

 public String[] sortSerials(String[] serialNumbers) {
  String[] ret = new String[serialNumbers.length];
  sortBySerial[] obj = new sortBySerial[serialNumbers.length];
  for( int i=0 ; ilt;obj.length ; i++ ){
   obj[i] = new sortBySerial(serialNumbers[i]); // ソートのためのオブジェクトに値をセット
  }
  Arrays.sort(obj); // これでオブジェクトがソートされたので、
  for( int i=0 ; ilt;ret.length ; i++ ){
   ret[i] = obj[i].str; // sortBySerialオブジェクトからStringのみを取得して、
  }
  return ret; // ソートした結果を返却する
 }

}

class sortBySerial implements Comparablelt;sortBySerialgt;{
 String str; // 文字そのもの
 int nStr; // 文字に現れる数字の合計
 public sortBySerial(String s){ // ソートのためのオブジェクトのコンストラクタ
  this.str = s;
  int n = 0;
  for( int i=0 ; ilt;s.length() ; i++ ){
   if( s.charAt(i) gt;= '0' && s.charAt(i) lt;= '9') n += s.charAt(i)-'0';
  }
  this.nStr = n;
 }
 public int compareTo(sortBySerial obj){ // ソートのルールを実装
  if( str.length() != obj.str.length() ){
   return str.length() - obj.str.length();
  }else if( nStr != obj.nStr ){
   return nStr - obj.nStr;
  }else{
   return str.compareTo(obj.str);
  }
 }
}

得点は204.29/250、1回のsubmitでシステムテストクリア。中央値は約97点と低め。ソートのルールが複雑なので、2重ループを1つのメソッドに書くより簡単だろうということで、Comparableを利用。過去に書いたComparableのコードを流用したので高速に解答できたはず。