yukicoder No.628 Tagの勢い
要はどうやってマップを値でソートするか、だと思う。
自分はマップを値でソートする方法が全く分かっていなかったので、これまでは、こういう問題が出たときには、キーに数値、値に文字列を入れてキーでソートして解いてきた。値でソートするよりも、キーでソートするほうがかなり簡単だからだ。
だけど今回はその数値(得点)が変動するので、この方法ではどうしようもなく、仕方なしに値でマップをソートする方法を頑張って考えてみることにした。以下に貼られるのは、Java初心者がなんとかしてマップを値でソートしようと格闘した形跡である。
import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { //ループ用変数nと、タグの得点を格納するハッシュマップを宣言。 //得点が同じ場合辞書順で小さいほうのタグを上位に表示してくださいとあるので、 //今回はTreeMapを使用した。 int n = sc.nextInt(); Map<String,Integer> map = new TreeMap<>(); //ループを回して、ハッシュマップのキーにタグ、値に得点を格納。 for (int i=0; i<n; i++) { //int型変数noの出番はなし。 int no = sc.nextInt(); int m = sc.nextInt(); int score = sc.nextInt(); for (int j=0; j<m; j++) { String tag = sc.next(); map.put(tag,map.getOrDefault(tag,0)); map.put(tag,map.get(tag)+score); } } //ハッシュマップの値でソートするにあたり、 //ハッシュマップの値を格納したリストを用意する。 List<Integer> list = new ArrayList<>(); for (Map.Entry<String,Integer> entry : map.entrySet()) { list.add(entry.getValue()); } //リストを昇順にソート。 Collections.sort(list,Comparator.reverseOrder()); //あとはリストを回しながら、ハッシュマップから昇順に値を取り出していけばいいのだが、 //ハッシュマップの値が重複していた場合、常に上方の値を取り出してしまう。 // //<fast,7> //<gateway,7> // //ハッシュマップにこのような並びでキーと値が格納されていた場合を考えてみる。 //ソート用のリストの中身は当然{7,7}になる。 //0番目の7をもとにして順番にハッシュマップを回した場合、検出されるのはもちろん<fast,7>だ。 //次、1番目の7をもとにして順番にハッシュマップを回した場合、検出されるのは<fast,7>。 //重複が発生してしまう。 //これを防ぐために、すでに検出したキーを保持するリストを作成。 List<String> list2 = new ArrayList<>(); //上の例でいくと、0番目の7をもとに<fast,7>を検出したら、 //検出済みリストにキー<fast>を追加する。 //検出済みリストに含まれているキーを除外するようにしてマップを回す。 //よって、1番目の7をもとにして検出するさいは、<fast,7>が除外され、 //値が同じである<gateway,7>を重複なく検出することができる。 //下の処理では、このようにして、 //検出→検出したものをリストに追加→リストに含まれないものを検出 //というふうにしてループを回していく。 //リストに格納された、得点の昇順に、ハッシュマップを回す。 for (int i=0; i<list.size(); i++) { for (Map.Entry<String,Integer> entry : map.entrySet()) { //ここの条件分岐が、初心者なりに工夫した点。 //&&左:現在調べているリストの値と、ハッシュマップの値が一致するか? //&&右:今から検出するキーは、検出済みリストに含まれていない(未検出)か? if (list.get(i)==entry.getValue() && list2.contains(entry.getKey())==false) { System.out.println(entry.getKey()+" "+entry.getValue()); //たったいま検出したキーを、検出済みキーのリストに追加。 list2.add(entry.getKey()); break; } } //タグを10個出力した時点で処理を終わる。 //タグが10個未満の場合は、リストの長さでループ回数を管理しているので、 //勝手にその数で終わってくれる。 if (i==9) {break;} } } }