frostar@wiki
CodeIQ:Nick
最終更新:
frostar
-
view
- 問題概要
- =でつながれたニックネームのリストからデータをグループ化する。
- データの一部
- William=Bill
- Arthur=Art
- Willy=Billy
- Bill=Billy
- 解法
- =でつながれたデータをためていけばいいのでHashSetなどのコレクションを利用します。
- 最終的にソートする必要があるので私はTreeSetで作成。
- グループが複数存在するため、TreeSetのArrayListを作ります。
- ArrayListじゃなくてもいいと思うけどTreeSetにしてソートするのはTreeSet同士のcompareがどうなってるかわからないのでちょっと避けました。
- 手順としては=でデータを分断して左辺か右辺がTreeSet内に存在してたらそこに挿入するということを繰り返せばいいので次のようなコードを設計(ソートや表示の部分は省略)。
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("nick.txt"),"UTF-8")); String line = br.readLine(); while (line != null) { String[] nick = line.split("="); Iterator<TreeSet<String>> i = nick_list.iterator(); boolean flag = false; while (i.hasNext()) { TreeSet<String> set = i.next(); if(set.contains(nick[0]) || set.contains(nick[1])){ set.add(nick[0]); set.add(nick[1]); flag = true; break; } } if(!flag){ TreeSet<String> nset = new TreeSet<String>(); nset.add(nick[0]); nset.add(nick[1]); nick_list.add(nset); } line = br.readLine(); }
- これで実行すると次のような回答が得られます。
- Arthur=Art
- Bill=Billy=William
- Billy=Willy
- 一見、正解のように見えますが2行目と3行目に同じBillyというニックネームが入っています。
- 別々に作成したTreeSetをつなぐようなニックネームが後から現れるために生じる現象です。
- 例えば今回の場合、Bill=Billyというデータが[Bill,William]と[Billy,Willy]というTreeSetをつなぐデータであるのにプログラムは先に見つけた[Bill,William]にデータを格納するようにしているため、このようになります。
- 複数のデータにまたがるデータを見つけたときにこれらを結合するようにすることで正解を得ることができます。
- そこで、次のようにプログラムを修正しました。
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("nick.txt"),"UTF-8")); String line = br.readLine(); while (line != null) { String[] nick = line.split("="); Iterator<TreeSet<String>> i = nick_list.iterator(); boolean flag = false; while (i.hasNext()) { TreeSet<String> set = i.next(); if(set.contains(nick[0]) || set.contains(nick[1])){ set.add(nick[0]); set.add(nick[1]); while (i.hasNext()) {//------------------------(1) TreeSet<String> set2 = i.next(); if(set2.contains(nick[0]) || set2.contains(nick[1])){ set.addAll(set2); i.remove(); } }//-----------------------------------------(1)' flag = true; break; } } if(!flag){ TreeSet<String> nset = new TreeSet<String>(); nset.add(nick[0]); nset.add(nick[1]); nick_list.add(nset); } line = br.readLine(); }
- コード中の(1)~(1)'の部分が追加した場所です。
- あるデータが所属するTreeSetを見つけた後も、それ以降のTreeSetを探し、そこにデータが所属する場合は最初のTreeSetに見つけたTreeSetのデータをすべて格納し、
- 見つけたTreeSetを削除しています。
- これにより、2つのTreeSetを1つに結合することができ、正解の
- Arthur=Art
- Bill=Billy=William=Willy
- というデータを得ることができます。