TopCoder SRM348 Div2 250Pts

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

ビリーは祖母の家に行こうとしている。そんな彼を手助けするために、母は従うべき指示をリストにしたものを彼のために書いた。各指示は"N"、"S"、"W"、"E"であり、それぞれ1ブロックだけ北、南、西、東に進めということを意味している。ビリーの住む町は無限に大きなマス目状の通りからなり、どの道も無限に伸びており、同じ方向にむかう隣あう2つの道の間の距離はいつも1ブロックである。ビリーの家と祖母の家はどちらもこの町の角にある。

ビリーは母が必ずしも最短経路を選んで指示を書いてくれないということを知っている。したがって、ビリーは最小の指示で祖母の家に向かえるような新しい指示のリストを作成したいと思っている。instというビリーの母が書いた指示を表した文字列が与えられたとき、ビリーの欲しい新しいリストを作成して返すメソッドを作成せよ。もし複数解があるなら、アルファベット順で最初に来るものを返すようにせよ。

私の解答はこちら。

public class OptimalList {

 public String optimize(String inst) {
  int[] dir = new int[2]; // 上下、左右に動くべき数を入れる
  for( int i=0 ; i<inst.length() ; i++ ){
   if( inst.charAt(i) == 'N'){
    dir[0]++;
   }else if( inst.charAt(i) == 'S'){
    dir[0]--;
   }else if( inst.charAt(i) == 'W'){
    dir[1]++;
   }else if( inst.charAt(i) == 'E'){
    dir[1]--;
   }
  }
  char col = dir[0] >= 0 ? 'N' : 'S'; // 動いた方向を決める
  char row = dir[1] >= 0 ? 'W' : 'E';
  StringBuilder ret = new StringBuilder();
  // アルファベット順にしないといけないのでcol、rowの文字を比較している
  if( col < row ){
   for( int i=0 ; i<Math.abs(dir[0]) ; i++ ) ret.append(col);
   for( int i=0 ; i<Math.abs(dir[1]) ; i++ ) ret.append(row);
  }else{
   for( int i=0 ; i<Math.abs(dir[1]) ; i++ ) ret.append(row);
   for( int i=0 ; i<Math.abs(dir[0]) ; i++ ) ret.append(col);
  }
  System.out.println(ret.toString());
  return ret.toString();
 }

}

得点は187.04/250、中央値は約201点。1回のsubmitでシステムテストクリア。NとS、WとEはペアであることに注目。例えばinst中のNとSの出現回数をカウントし、その回数の差だけ動けば移動距離は最短にできる。WとEの場合も同様である。