「第7回 オフラインリアルタイムどう書く」へなちょこ解答(Java)
昨日は「第7回 オフラインリアルタイムどう書く」へ行ってきました。
- オフラインリアルタイムどう書くとは
- 鍋谷さんが出してくださるお題を、参加者が好きなプログラミング言語で解いて楽しむ会です。
今回は、「のんびり座りたい」です!
- 問題と皆さんの解答: http://qiita.com/items/4364285801d1c9f370a1
めずらしく時間内に解き終わったので、懇親会のお酒が美味しかったです。やりましたね。
自分の解答
(下は書き直したバージョンです。時間内で書いたコードはこちら→ http://qiita.com/items/42c1e153436d74dea6e6)
import static org.junit.Assert.assertEquals; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import org.junit.Test; /** * 問題: http://qiita.com/items/4364285801d1c9f370a1 */ public class SelectChair { protected final char EMPTY = '-'; public String solve(final String string) throws IllegalArgumentException { String[] split = string.split(":"); char[] chairs = new char[Integer.valueOf(split[0])]; Arrays.fill(chairs, EMPTY); char[] inOut = split[1].toCharArray(); for (char each : inOut) { if (Character.isUpperCase(each)) { int recomended = searchChair(chairs); chairs[recomended] = each; } else { int awayIndex = awayChair(chairs, each); chairs[awayIndex] = EMPTY; } } String result = ""; for (char each : chairs) { result += each; } return result; } protected int searchChair(final char[] chairs) { List<Integer> secondary = new ArrayList<>(); List<Integer> guttari = new ArrayList<>(); for (int i = 0; i < chairs.length; i++) { char tmpChair = chairs[i]; if (tmpChair == EMPTY) { if (chairs.length == 1) { return i; } else if ((i == 0 && EMPTY == chairs[i + 1]) || (i == chairs.length - 1 && EMPTY == chairs[i - 1])) { return i; } else if ((i == 0 && EMPTY != chairs[i + 1]) || (i == chairs.length - 1 && EMPTY != chairs[i - 1])) { secondary.add(i); } else if (EMPTY == chairs[i + 1] && EMPTY == chairs[i - 1]) { return i; } else if (EMPTY == chairs[i + 1] || EMPTY == chairs[i - 1]) { secondary.add(i); } else { guttari.add(i); } } } if (secondary.isEmpty() == false) { return Collections.min(secondary); } else if (guttari.isEmpty() == false) { return Collections.min(guttari); } throw new IllegalArgumentException("There are no seats left."); } protected int awayChair(final char[] chairs, final char c) throws IllegalArgumentException { for (int i = 0; i < chairs.length; i++) { if (chairs[i] == Character.toUpperCase(c)) { return i; } } throw new IllegalArgumentException(Character.toUpperCase(c) + " hasn't seated."); } }
- 上のコードと、テストコード https://gist.github.com/4700676
書き直していて、Javaの文法に関してちょっと分からないことがあったので、それは別記事にしようと思います。書きました。 http://d.hatena.ne.jp/torazuka/20130203/array
考え方のメモ
- 座席配列(席数==要素数のchar配列)を作成し、空席を表わすハイフンで初期化します
- 入力値が大文字か小文字かを見て、着席か離席かを判定します
着席の場合は、座席を左から走査して、空席を見つけたら両隣の状態を調べます。
- 座席が全部で1席のとき、空席==座る席なので、primaryリストに席を登録します(例外的な処理)
- 空席が、座席の先頭あるいは末尾の場合
- 隣が空いていれば、primaryリストに席を登録します
- 隣が埋まっていれば、secondaryリストに席を登録します
- 空席が、座席の先頭あるいは末尾でない場合
- 両隣が空いていれば、primaryリストに席を登録します
- 片方が埋まっていれば、secondaryリストに席を登録します
- 両隣が埋まっていれば、guttariリストに席を登録します
- guttari < secondary < primary の優先順で、席を提示します
離席の場合は、入力値の大文字が登録されている座席インデックスを座席配列から検索し、そこにハイフンを挿入します。
# 書き直したバージョンでは、primaryリストは不要になり、消えてしまいました。せっかくダジャレにしたのになぁ…
使い忘れていたJava標準API
時間内に書いたコードでは、いくつかの標準APIを使い忘れていました。余計なコードを書くのに時間を費やしたし、自分で書いたことでバグる可能性も上げてしまったと思います。
次からは、やりたい処理を思いついたらいきなり書くのではなく、こういうのは標準APIにあったなーとか、確かではないけど何となくありそうだよなーとか、落ち着いて考えるようにしたいです。
忘れていたAPIは、次のものでした。
リストの空判定
if (primary.isEmpty() == false) { // primary は List<Integer> のインスタンス (略)
これは、発表中に指摘いただきました。
リストの最小値の取得
result = Collections.min(primary);
文字列のchar配列化
char[] inOut = split[1].toCharArray();
配列要素の一斉初期化
char配列の各要素を「-(ハイフン)」で埋める処理です。
String[] split = string.split(":"); char[] chairs = new char[Integer.valueOf(split[0])]; Arrays.fill(chairs, '-');
ほかの方の解答について
多くの方が、配列の先頭の1つ前と末尾の1つ後に要素を足して、すべての要素を同じように扱う方法を使っていて、勉強になりました。その方法を使えば、自分の解答の見にくいif文も、もう少し何とかなる気がします。
あとは、hirataraさんの正規表現を使った解法には、やられた感がありました。
というわけで、今回も楽しかったです! 鍋谷さん、皆さん、ありがとうございました。