マップを値でソートする方法

マップを値でソートする方法については以前記事にしたのだけれども、

マップを値でソートするメソッド - Java初心者の競技プログラミング日記

あまりに冗長すぎるのでもっと短く書ける方法を探した。見つかった。

//昇順
map = map.entrySet().stream()
.sorted(Entry.<String,Integer>comparingByValue())
.collect(Collectors.toMap(Entry::getKey,Entry::getValue,(e1, e2)->e1,LinkedHashMap::new));

//降順
map = map.entrySet().stream()
.sorted(Entry.<String,Integer>comparingByValue().reversed())
.collect(Collectors.toMap(Entry::getKey,Entry::getValue,(e1, e2)->e1,LinkedHashMap::new));

java.util.Map.Entry と java.util.stream.Collectors をインポートしてある。

以下のサイトを参考にしました
How to Sort Map by values in Java 8 using Lambdas and Stream - Example Tutorial | Java67

自作クラスの入ったリスト・配列をソートする方法

まずはリスト。

class Point {
	int x;
	int y;
	char color;
	Point(int a, int b, char c) {
		this.x = a;
		this.y = b;
		this.color = c;
	}
	int getX() {
		return this.x;
	}
	int getY() {
		return this.y;
	}
	char getColor() {
		return this.color;
	}
}

クラスPointが入っているリストlistを、それぞれのメンバ変数についてソートしてみる。

//xで昇順ソート
list.sort(Comparator.comparing(Point::getX));

//yで降順ソート
list.sort(Comparator.comparing(Point::getY).reversed());

//colorで昇順ソート
list.sort(Comparator.comparing(Point::getColor));

//xで昇順ソート、xが同じ場合はyで降順ソート、yも同じ場合はcolorで昇順ソート
list.sort(Comparator.comparing(Point::getX)
		.thenComparing(Point::getY).reversed()
		.thenComparing(Point::getColor));

メンバ変数xでソートする場合、xを取得するメソッドがクラス側に必要。

thenComparingで同じ値だった場合のソート条件を追加できる。

また、import static java.util.Comparator.* とインポートすることでComparatorの部分を省略できる。

次に配列。

class Person {
	String name;
	int age;
	Person(String s, int n) {
		this.name = s;
		this.age = n;
	}
	String getName() {
		return this.name;
	}
	int getAge() {
		return this.age;
	}
}

クラスPersonが入っている配列arを、それぞれのメンバ変数についてソートしてみる。

//nameで昇順ソート
Arrays.sort(ar,Comparator.comparing(Person::getName));

//ageで降順ソート
Arrays.sort(ar,Comparator.comparing(Person::getAge).reversed());

追記。以前、文字列の長さでソートする問題があったことを思い出したので、それもやってみる。

List<String> list = new ArrayList<>() と宣言した単純なString型のリストであれば、

・list.sort(Comparator.comparingInt(String::length));

とすることで、文字列の長さが短い順でソートできる。

では、上記のようなPerson型のオブジェクトが入っているリストを、nameの長さでソートする方法は？

少し調べてみたが分からない。Person::getName.length など色々試してみたがダメ。

解決策としては、nameの長さを変数nameLengthに入れておいて、

・list.sort(Comparator.comparing(Person::nameLength));

とすればいいと思う。

以下のサイトを参考にしました
Javaで自作クラスをソートする3通りの方法【Java8】 - 俺とプログラミング
(o1, o2) -> o1 - o2 なんて呪文はもうやめて！ - Java8でのComparatorの使い方 - Qiita

AtCoder Beginner Contest 091

A - Two Coins

A+B>=C ? "Yes":"No"

B - Two Colors Card Game

import java.util.*;
import static java.lang.System.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		HashMap<String,Integer> map = new HashMap<>();
		int n = sc.nextInt();
		String s;
		for (int i=0; i<n; i++) {
			s = sc.next();
			map.put(s,map.getOrDefault(s,0));
			map.put(s,map.get(s)+1);
		}
		int m = sc.nextInt();
		for (int i=0; i<m; i++) {
			s = sc.next();
			map.put(s,map.getOrDefault(s,0));
			map.put(s,map.get(s)-1);
		}
		int max = 0;
		for (Map.Entry<String,Integer> e : map.entrySet()) {
			max = Math.max(max,e.getValue());
		}
		out.println(max);
	}
}

最初のn回のループでは、文字列とその出現回数をマップに記録する。
次のm回のループでは、受け取った文字列がマップに含まれているなら出現回数から1引く。
このようにして入力を受け取ったあとの、マップ内の値の最大値が答え。最大値が0未満なら0。

C - 2D Plane 2N Points

今回もC問題はACできなかった。解説を読んでみる。

1．x座標、y座標、色。この3つのメンバ変数を持つクラスを作成する
2．ArrayListに、上記の3つのメンバ変数を持ったすべての赤座標オブジェクトと青座標オブジェクトを入れる
3．listをx座標でソートする
4．0～list.size() までループを回して、先頭の座標から見ていく
4-1．座標が赤ならsetに追加
4-2．座標が青なら、取得した青座標よりもy座標が小さい赤座標をsetの中から探す。そのうち、もっともy座標が大きいものを削除。
5．リストの末尾まで処理したあと、N-list.size() をしたものが答え。

解法を見てなるほどと思ったが、listに入っているオブジェクトをメンバ変数の大小でソートする方法が分からない。特殊なソートのやり方が全然分かっていないので勉強しないとダメ。Comparatorとか。

D - Two Sequences

問題を見ていない

まとめ

特殊なソートについては早急に学ぶ必要があると感じた。マップを値でソートするやり方についてもかなり怪しいので、それも見直す必要がある。

No.351 市松スライドパズル

逆シミュレーションする。

求めたいのは「最終的に左上のマスが何色であったか」なので、「最終盤面の左上のマスは、最初の盤面のどの位置から運ばれてきたか」を考える。

最終盤面の左上のマスの座標をx=0,y=0とおく。操作を後ろから順に行っていって、Rの番号が現在のxと一致していたらxから1引く。xがもし負の値になったら（盤面の左端からはみ出てしまったら）、Wを足す（盤面の右端におく）。同様に、Cの番号が現在のyと一致していたらyから1引く。負の値ならHを足す。

Rの番号がxと一致しない、あるいはCの番号がyと一致しない場合は何もしない。

全ての操作を処理し終えたときの（x,y）が「最初の盤面における、最終盤面の左上のマスの位置」である。このマスが、n回の操作のすえに最終的に左上まで運ばれてくるということになる。つまり、最初の盤面におけるマス（x,y）が何色かを考えればよい。これは、x+yが偶数なら白、x+yが奇数なら黒になる。

import java.util.*;
import static java.lang.System.*;
 
public class Blog {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int H = sc.nextInt();
		int W = sc.nextInt();
		int n = sc.nextInt();
		Operation[] op = new Operation[n];
		for (int i=0; i<n; i++) {op[i] = new Operation(sc.next().charAt(0),sc.nextInt());}
		
		int x = 0, y = 0;
		for (int i=n-1; i>=0; i--) {
			if (op[i].RC=='R' && op[i].num==y) {
				x--;
				x += x<0?W:0;
			}
			else if (op[i].RC=='C' && op[i].num==x) {
				y--;
				y += y<0?H:0;
			}
		}
		
		out.println((x+y)%2==0?"white":"black");
	}
}

class Operation {
	char RC;
	int num;
	Operation (char c, int n) {
		this.RC = c;
		this.num = n;
	}
}

二分探索

二分探索は、ソートされた配列の中から、特定の要素を高速で見つけ出すアルゴリズムである。

線形探索（先頭から末尾まで順番に判定していく）とは桁違いの速さで、具体的には、要素数1000000のとき線形探索では1000000回の判定が必要なのに対して、二分探索ではたった20回で済む。

この20回という回数はどこから来ているのかというと、要素数を2^nで表したときのnから。判定回数は整数値なので、要素数が100なら2^7=128（7回）、要素数が1000000なら2^20=1048576（20回）となる。

まずはシンプルな二分探索を実装してみる。

import java.util.*;
import static java.lang.System.*;

public class Blog {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int[] ar = {45,20,10,30,5,50,15,25,35,40};
		Arrays.sort(ar); //ソートする
		
		//ソートされた配列を表示
		for (int e:ar) {out.print(e+" ");} out.println();
		
		//ここから二部探索
		//L,Rを宣言
		int L = 0;
		int R = ar.length; //Rの初期値は要素数
		int target = 30;
		
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] == target) {
				out.println(target+"は"+(M+1)+"番目です");
				break;
			}
			else if (ar[M] > target) {R = M;}
			else if (ar[M] < target) {L = M+1;}
		}
	}
}

出力

次に、「target以下・target以上、target未満・targetより大きい要素はそれぞれ配列中に何個あるか」を調べる二分探索を書いてみたい。なぜこれを書く気になったかというと、以下の問題を解いたから。

C - Snuke Festival

import java.util.*;
import static java.lang.System.*;

public class Blog {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int[] ar = {45,20,10,30,5,50,15,25,35,40};
		Arrays.sort(ar);
		for (int e:ar) {out.print(e+" ");} out.println();
		
		
		//以下
		int target = 30;
		int L = 0;
		int R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] > target) {R = M;}
			else if (ar[M] <= target) {L = M+1;} //以下・以上を調べるときはこちらに等号をつける
		}
		out.println("30以下の値は"+L+"個あります");
		
		
		//以上
		target = 30;
		target--; //target以上を調べる場合は、targetから1引いたものを使う
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] > target) {R = M;}
			else if (ar[M] <= target) {L = M+1;}
		}
		out.println("30以上の値は"+(ar.length-L)+"個あります");
		
		
		
		
		
		//未満
		target = 30;
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] >= target) {R = M;} //未満・より大きいを調べるときはこちらに等号をつける
			else if (ar[M] < target) {L = M+1;}
		}
		out.println("30未満の値は"+L+"個あります");
		
		
		//より大きい
		target = 30;
		target++; //targetより大きい値の個数を調べるときは、targetに1足したものを使う
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] >= target) {R = M;} //未満・より大きいを調べるときはこちらに等号をつける
			else if (ar[M] < target) {L = M+1;}
		}
		out.println("30より大きい値は"+(ar.length-L)+"個あります");
		
		
	}
}

出力

追記：Arrays.binarySearchというメソッドを見つけた。Arrays.binarySearch(ar,n)とすることで、配列ar内にあるnの位置を戻り値として返してくれる。機能が限られているのであまり使い道はないかもしれない。ざっと調べてみたところ、配列内に同じ値がある場合はどれが検索されるか不定とあったので、重複のない配列でのみ用いるのがよさそう。

再帰関数入門・迷路探索編

再帰関数を用いて迷路を探索し、スタートからゴールにたどりつけるかどうかを判定する。

使用するのは以下の問題。

A - 深さ優先探索

import java.util.*;
import static java.lang.System.*;

public class Blog {
	static Scanner sc = new Scanner(System.in);
	
	static int H=sc.nextInt(),W=sc.nextInt();
	static char[][] map = new char[H][W];
	static boolean[][] memo = new boolean[H][W];
	static int sy,sx;
	static int gy,gx;
	
	public static void main(String[] args) {
		
		for (int i=0; i<H; i++) {
			String s = sc.next();
			map[i] = s.toCharArray();
			for (int j=0; j<s.length(); j++) {
				if (s.charAt(j)=='s') {sy = i; sx = j;}
				else if (s.charAt(j)=='g') {gy = i; gx = j;}
			}
		}
		rec(sy,sx);
		System.out.println(memo[gy][gx]?"Yes":"No");
		
		//ここから探索結果表示
		for (int i=0; i<H; i++) {
			for (int j=0; j<W; j++) {
				out.print(memo[i][j]==true?"o":"x");
			}
			out.println();
		}
		//ここまで
	}

	static void rec(int y, int x) {
		if (y<0 || x<0 || H<=y || W<=x) {return;}
		if (map[y][x]=='#' || memo[y][x]) {return;}
		memo[y][x] = true;
		rec(y,x+1);
		rec(y,x-1);
		rec(y+1,x);
		rec(y-1,x);
	}
	
}

入力例4

まず、メインメソッドからスタート地点を引数にして再帰関数を起動する。

その後は、引数の座標に対して、

迷路の範囲外の場合　→　何もしない
壁の場合、あるいは座標が訪問済みの場合　→　何もしない
それ以外　→　訪問済みかどうかを記録する配列memoにtrueを代入、上下左右に分岐

という流れで処理していく。

処理が一通り終わったら（スタート地点から到達することができる全ての座標を探索したら）、ゴールが訪問済みになっているかどうかを調べて、訪問済みならYes（到達可能）、未訪問ならNo（スタート地点からは到達不可能）を出力する。

迷路探索のアルゴリズムでは、以前、幅優先探索のものを紹介した。

迷路探索メソッド - Java初心者の競技プログラミング日記

深さ優先と幅優先、どちらを使えばいいかは問題による。調べてみたところ、最短歩数を求めるような問題では、深さ優先探索は使えないらしい。また、ゴール地点がスタート地点から近ければ近いほど、幅優先探索のほうが有利になるらしい。

結局のところどちらを使えばいいのか……おそらく、単純にゴールに到達可能かどうかを調べるだけなら、深さ優先探索でいいと思う。コードも短くて済むし。高度なことをやる場合、たとえばyukicoderのコレ（No.424 立体迷路 - yukicoder）や、コレ（No.157 2つの空洞 - yukicoder）のような問題を解くときに、幅優先探索を使うのだと思う。

ArrayDequeとLinkedList

基本的にはArrayDequeとLinkedListのどちらも、キュー・スタックとして使えるようだ。

先頭に挿入：addFirst
末尾に挿入：addLast

先頭を取得：getFirst
末尾を取得：getLast

先頭を取得して削除：removeFirst
末尾を取得して削除：removeLast

ここまではArrayDequeとLinkedListで共通しているメソッド。

LinkedListには、これらのメソッドのほかにもindexOfとlastIndexOfがある。ArrayDequeにはない。

優先度つきのPriorityQueueというクラスもあるらしい（使ったことない）。

【補足】
・挿入、削除、取得を両端でしか行わない場合、ArrayDequeのほうが高速に動作するらしい。
・配列の中間にアクセスする場合（containsやindexOfなど）は、LinkedListのほうが速いらしい。
・先頭から2つの要素を順に取得したいというような場合、

　int a = deque.getFirst();
　deque.removeFirst();
　int b = deque.getFirst();
　deque.removeFirst();

　とするのではなく、removeFirstを上手く使って、

　int a = deque.removeFirst();
　int b = deque.removeFirst();

　とすることで短く簡潔に書ける。