Two Colors Card Game [AtCoder Beginner Contest 091 B] - 文系プログラマーのプログラミング備忘録

まず問題を整理します。

・青いカードがn枚、赤いカードがm枚ある
・好きな文字列を一つ選ぶ
・選んだ文字列が書かれている青いカードは何枚あるか数える。1枚につき1円を得る
・同様に、選んだ文字列が書かれている赤いカードは何枚あるか数える。1枚につき1円を失う
・得られるお金を最大化せよ

といった感じでしょうか。

解説にある通り、得られるお金（収支）が0円を下回ることはありません。青いカードにも赤いカードにも書いていない文字列を選べば、お金のやり取りは発生しないからですね。そしてこれも解説にあるように、選ぶ対象となり得る文字列は、少なくとも一枚以上の青いカードに書かれている文字列に限られます。なぜなら、赤いカードにのみ書かれている文字列を選んでも、お金が減るだけだからです。

これらのことから、解説では、青いカードに書いてある文字列をそれぞれ選んだときに何円貰えるかを調べて、その最大値を出力すればよい、となっています。

もちろんこの方法で解くべきですし、そのほうが実行速度も速いのですが、ここはあえて勉強のために回りくどい方法で記述してみることにしました。以下がそのコードになります。

//abc091-b

import java.util.*;
import java.util.stream.Collectors;

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();
		for (int i=0; i<n; i++) {
			String s = sc.next();
			map.put(s, map.getOrDefault(s,0)+1);
		}
		
		int m = sc.nextInt();
		for (int i=0; i<m; i++) {
			String s = sc.next();
			map.put(s, map.getOrDefault(s,0)-1);
		}
		
		map = map.entrySet().stream()
				.sorted(Map.Entry.<String,Integer>comparingByValue().reversed())
				.collect(Collectors.
						toMap(Map.Entry::getKey,Map.Entry::getValue,(e1, e2)->e1,LinkedHashMap::new));
		
		System.out.println(Math.max(map.values().stream().findFirst().get(), 0));
		
	}
}

やっていることは「青・赤それぞれのカードに登場する全ての文字列について、選んだときに得られるお金を計算し、最大の値を出力する」というものです。

そのためにmapを使います。1個目、および2個目のループの中には

map.put(s, map.getOrDefault(s,0)+1);
map.put(s, map.getOrDefault(s,0)-1);

という記述がありますが、この部分では

・mapに文字列sはキーとして存在するか？
　→存在しないなら、文字列sをキーとしてmapに登録し、値を1とする
　→存在するなら、文字列sに対応する値を1増やす（赤いカードなら1減らす）

という処理をおこなっています。本来であればmap.containsKey()としてif文で分岐させて書くところを、このように1行で簡潔に記述できるので、個人的にとても気に入っています。

その次、何かゴチャゴチャしている部分では、mapを値で降順ソートしています。この部分と、それから次の部分はコピペしたものをそのまま使わせていただきました。streamを上手く使うとこんな処理ができるんだな、といった程度にしか理解していないので、暇があれば分析してみたいところです。

最後の出力部分では、これまたstreamを使って「mapの先頭にある要素の値」と0を比較し、大きいほうを出力しています。以前は拡張for文を1回だけ回してbreakするというやり方で先頭の要素を取得していたのですが、この書き方のほうがわかりやすいですよね。また、values()の部分をkeySet()にすることで、同様に「mapの先頭にある要素のキー」も取得できます。