Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-08SRM497(DIV1)

PermutationSignature

|  PermutationSignature - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  PermutationSignature - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11115

本番中では方針が浮かばず、書いちゃ消し、書いちゃ消しを繰り返した。

サンプルを見たら、D の部分だけ数字を入れ替えればいいのでは、と思った。

数列の端から端までをlen回なめる、バブルソート的な感じで実装。


問題文中の

If no such permutation exists, return an empty int[] instead.

(該当する数列が存在しない場合は、空の配列を返せ)

という文言が妙に気になり、そんなパターンあるかいなと思いつつも

疑心暗鬼にテストを繰り返し、時間がかかってしまった。


public class PermutationSignature {

  public int[] reconstruct(String signature) {
    int len = signature.length();
    int data[] = new int[len + 1];
    for (int i = 0; i < len + 1; i++) {
      data[i] = i + 1;
    }

    for (int a = 0; a < len; a++) {
      for (int i = 0; i < len; i++) {
        if (signature.charAt(i) == 'D' && data[i] < data[i + 1]) {
          int x = data[i];
          data[i] = data[i + 1];
          data[i + 1] = x;
        }
      }
    }
    return data;
  }
}