Mapをキーでソートする方法

マップをソートするには、まずキーをObject型の配列に格納し、配列をソートして、その配列をもとにしてマップから順番に値を取り出していく……ということを以前はやっていたのだが、よくよく調べてみると、自動でソートしてくれるTreeMapなるものが存在しているらしい。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		Map<Integer,String> map = new TreeMap<>();
		map.put(1,"one");
		map.put(3,"three");
		map.put(5,"five");
		map.put(4,"four");
		map.put(2,"two");
		
		map.forEach((key,value) -> System.out.println(key+":"+value));
		
		/*
		
		1:one
		2:two
		3:three
		4:four
		5:five
		
		*/
	}
}

今回のように、コンストラクターに何も渡さなければ昇順に並ぶ。
Comparatorを渡して降順にすることもできる。

昇順：TreeMap<>();
降順：TreeMap<>(Comparator.reverseOrder());

値でソートする方法についてはまだほとんど分かっていないので、理解できたら記事にしたい。

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;}
		}
	}
}

二点間の距離を求めるメソッド

二点間の距離には、ユークリッド距離とマンハッタン距離の二種類がある。

・ユークリッド距離：二点間の最短距離
・マンハッタン距離：座標軸に平行にのみ移動できる場合の最短距離

以下のサイトで二種類の距離について詳しく解説されています
L1距離（マンハッタン距離）の意味と性質 | 高校数学の美しい物語

//ユークリッド距離
static double GetDistance (double x1, double y1, double x2, double y2) {
	double d = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
	return d;
}


//マンハッタン距離
static double GetManhattan (double x1, double y1, double x2, double y2) {
	double d = Math.abs(x1-x2)+Math.abs(y1-y2);
	return d;
}

Javaプログラミング関連のウェブサイト

僕がよく参考にさせてもらっている、初心者がJavaプログラミングをするときに助けになるであろうウェブサイトへのリンクをまとめたものです。

・コレクション（List,Map,Set)
Javaコレクションクラスメモ(Hishidama's Java Collection Memo)

・正規表現
正規表現の基礎
Java正規表現メモ(Hishidama's Java Regular Expression Memo)

・文字コード
ASCII文字コード - IT用語辞典

・メソッド名
うまくメソッド名を付けるための参考情報 - Qiita

substringの範囲

いまいち分かりにくい、substringの範囲について。
例えば次のプログラム。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = "abcde";
		System.out.println(s.substring(1,3));
	}
}

文字列「”abcde”」に対してsubstring(1,3)とすると、「bc」が抜き出される。

プログラミング言語では最初の要素が0で表されるので、文字列abcdeは0～4の数字で表されることになる。つまり、1文字目は「b」であり、3文字目は「d」である。それなのにどうして「bcd」ではなく「bc」が抜き出されるのか。

まず基本的なこととして、文字列sにおいてsubstringで指定できる範囲は「0～s.length()」になる。つまり、abcdeなら0～5の範囲で指定できる。そう、abcdeは0～4の数字で表されるのに、substringでは0～5の範囲で抜き出せるのだ。いったい処理はどうなっているのか。僕が思うに、おそらく以下のような基準に基づいて抜き出している。

0 a 1 b 2 c 3 d 4 e 5

0～5までの数字が、substringで指定可能な範囲で、その間に文字列が挟まれているという具合だ。このとき、substring(1,3)とすると、1と3の間にある文字は「bc」になる。同様に、先頭の1文字を抜き出すならsubstring(0,1)になるし、末尾の1文字を抜き出すならsubstring(4,5)になる。末尾の1文字については、substring(s.length()-1,s.length())とも書ける。

判明した基準をもとにして、いくつかの例題を解き、それを確かめてみたいと思う。

【１、文字列strのn文字目を1文字抜き出す場合】

・String n = str.substring(n,n+1);

抜き出すのが1文字だけの場合、char型が使えるので、
・char n = str.charAt(n);
としても抜き出せる。

また、n文字目からm文字分抜き出したい場合は、
・String m = str.substring(n,n+m);
とすればよい。

【２、文字列を真ん中で二分する場合】

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String a = "1113555"; //文字列の長さが奇数の場合
		String b = "222444"; //文字列の長さが偶数の場合
		
		//文字列aを左右に分割（中央の文字はスルー）
		String a_L = a.substring(0,a.length()/2);
		String a_R = a.substring(a.length()/2+1,a.length());
		
		//文字列bを左右に分割（こっちは二分可能）
		String b_L = b.substring(0,b.length()/2);
		String b_R = b.substring(b.length()/2,b.length());
		
		System.out.println(a_L+":"+a_R);
		//output = 111:555
		
		System.out.println(b_L+":"+b_R);
		//output = 222:444
	}
}

【補足】奇数長の文字列strから中央の文字だけ抜き出す場合
・substring(str.length()/2,str.length()/2+1);

【３、先頭からn文字、末尾からn文字抜き出す場合】

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String a = "oooxxx"; 
		String b = "???!!!"; 
		int n = 3;
		
		//aの先頭からn文字抜き出す
		String a_top = a.substring(0,n);
		
		//bの末尾からn文字抜き出す
		String b_last = b.substring(b.length()-n,b.length());
		
		System.out.println(a_top);
		//output = ooo
		
		System.out.println(b_last);
		//output = !!!
	}
}

memo

いつかは記事にしたい競プロ関係のアルゴリズムとかjavaの文法とかの備忘録です。
自分用です。

【メソッド・アルゴリズム】
・二点間の距離（ユークリッド距離とマンハッタン距離）
・LinkedHashMapを上手く使えば、山札から一枚を一番上に持ってくる動作とか、何か色んなことができそう。
・ハッシュマップを値でソートするメソッドをとりあえずでいいから作る

【java文法】
・型変換（全パターン、char→intとかdouble→Stringとかそういうのも）
　データ型の分類を跨ぐ場合（intとstring）と、跨がない場合（charとstring）で分ける
・分かってそうで分かっていないStringBuilderの文法
・よく使う正規表現
・切り上げと切り捨てについて
・substring()やらdelete()やら、対象位置がやたら分かりにくい関数の説明

大文字と小文字を逆転させるメソッド

英語アルファベットのみで構成される文字列の、大文字と小文字を逆転させるメソッド。

static String CaseReverse (String s) {
	StringBuilder sb = new StringBuilder();
	for (int i=0; i<s.length(); i++) {
		char c = s.charAt(i);
		if (Character.isUpperCase(c)) {
			c += 32;
			sb.append(c);
		}
		else {
			c -= 32;
			sb.append(c);
		}
	}
	return sb.toString();
}

Character.isUpperCase(c)の部分は、cが大文字ならtrue、cが小文字でならfalseを返す。

toUpperCase(),toLowerCase()を使って変換してもよかったのだが、こちらのほうがなんとなく処理が速そうなので、charの値を足し引きすることによって大文字と小文字を逆転させるようにした。

ASCII文字コードでは、大文字のAが65、小文字のaが97となっているので、小文字から32を引けば大文字になり、大文字に32を足せば小文字になる。

Character.isUpperCase()を使わない場合は、cの値が65～90（大文字）であれば32を足す、97～122であれば32を引くというふうに、cの範囲で条件分岐させる。

文字列に半角スペース（" "）や各種記号（"-","?","!"）が含まれている場合はエラーが発生するので、それらの文字をスルーしたい場合はここに条件分岐を付け加える。