Ruby と Perl と Java で解く AtCoder ABC 111 C ハッシュのソート

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder Beginner Contest 111 C - /\/\/\/](https://atcoder.jp/contests/abc111/tasks/arc103_a)*
<font color="green">Difficulty: 822</font>

今回のテーマ、ハッシュのソート
# Ruby
重複した要素、とくればハッシュですよね。
解法は前回の、*[Ruby と Perl と Java で解く AtCoder ABC 113 C](https://qiita.com/superrino130/items/21111248bb21a4dac0b2)* に似た問題です。

```ruby.rb
n = gets.to_i
v = gets.split.map(&:to_i)
p = Hash.new(0)
q = Hash.new(0)
n.times do |i|
  p[v[i]] += 1 if i.even?
  q[v[i]] += 1 if i.odd?
end
ps = Hash[p.sort_by{|k, v| -v}].keys
qs = Hash[q.sort_by{|k, v| -v}].keys
x, y, ans = 0, 0, n / 2
f = false
ps.size.times do |i|
  x = ps[i]
  qs.size.times do |j|
    if x != qs[j]
      y = qs[j]
      f = true
      break
    end
  end
  break if f
end
ans = n - p[x] - q[y] if f
x, y = 0, 0
f = false
qs.size.times do |i|
  x = qs[i]
  ps.size.times do |j|
    if x != ps[j]
      y = ps[j]
      f = true
      break
    end
  end
  break if f
end
ans = n - q[x] - p[y] if f && ans > n - q[x] - p[y]
puts ans
```
```hash.rb
ps = Hash[p.sort_by{|k, v| -v}].keys
```
ABC113C では *Perl* 風のソートでしたが、今回は *Ruby* 風のソートにしてみました。
# Perl
```perl.pl
chomp (my $n = <STDIN>);
chomp (my @v = split / /, <STDIN>);
my (%p, %q);
for my $i (0..$n-1) {
  if ($i % 2 == 0) {
    $p{$v[$i]}++;
  } else {
    $q{$v[$i]}++;
  }
}
my @ps = sort {$p{$b}<=>$p{$a}} keys %p;
my @qs = sort {$q{$b}<=>$q{$a}} keys %q;
my ($x, $y) = (0, 0);
my $ans = $n / 2;
my $f = 0;
for my $i (0..$#ps) {
  $x = $ps[$i];
  for my $j (0..$#qs) {
    if ($x != $qs[$j]) {
      $y = $qs[$j];
      $f = 1;
      last;
    }
  }
  last if $f;
}
$ans = $n - $p{$x} - $q{$y} if $f;
($x, $y) = (0, 0);
my $f = 0;
for my $i (0..$#qs) {
  $x = $qs[$i];
  for my $j (0..$#ps) {
    if ($x != $ps[$j]) {
      $y = $ps[$j];
      $f = 1;
      last;
    }
  }
  last if $f;
}
$ans = $n - $q{$x} - $p{$y} if $f && $ans > $n - $q{$x} - $p{$y};
print "$ans\n";
```
```hash.pl
my @ps = sort {$p{$b}<=>$p{$a}} keys %p;
```
*Perl* のハッシュは、シンプルかつ速いイメージがあります。
# Java
```java.java
import java.util.*;
import java.util.stream.Collectors;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Map<Integer, Integer> p = new HashMap<>();
        Map<Integer, Integer> q = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int v = Integer.parseInt(sc.next());
            if (i % 2 == 0) {
                if (p.containsKey(v)) {
                    p.put(v, p.get(v) + 1);
                } else {
                    p.put(v, 1);
                }
            } else {
                if (q.containsKey(v)) {
                    q.put(v, q.get(v) + 1);
                } else {
                    q.put(v, 1);
                }
            }
        }
        sc.close();

        Map<Integer, Integer> ps = p.entrySet().stream()
                .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed()
                        .thenComparing(Map.Entry.comparingByKey()))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
        Map<Integer, Integer> qs = q.entrySet().stream()
                .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed()
                        .thenComparing(Map.Entry.comparingByKey()))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));

        List<Integer> pss = new ArrayList<>(ps.keySet());
        List<Integer> qss = new ArrayList<>(qs.keySet());
        int x = 0, y = 0, ans = n / 2;
        boolean f = false;
        for (int i = 0; i < pss.size(); i++) {
            x = pss.get(i);
            for (int j = 0; j < qss.size(); j++) {
                if (x != qss.get(j)) {
                    y = qss.get(j);
                    f = true;
                    break;
                }
            }
            if (f)
                break;

        }
        if (f)
            ans = n - p.get(x) - q.get(y);
        x = 0;
        y = 0;
        f = false;
        for (int i = 0; i < qss.size(); i++) {
            x = qss.get(i);
            for (int j = 0; j < pss.size(); j++) {
                if (x != pss.get(j)) {
                    y = pss.get(j);
                    f = true;
                    break;
                }
            }
            if (f)
                break;

        }
        if (f && ans > n - q.get(x) - p.get(y))
            ans = n - q.get(x) - p.get(y);
        System.out.println(ans);
    }
}
```
*Java* ハッシュのソートは、実装がすごく大変。普段 *Java* やっている方は、クラスでソートしているのでしょうか。

||Ruby|Perl|Java|
|:--:|:--:|:--:|:--:|
|コード長|694 Byte|808 Byte|2646 Byte|
|実行時間|164 ms|131 ms|649 ms|
|メモリ|24808 KB|28616 KB|54320 KB|
# まとめ
+ ABC 111 C を解いた
+ Ruby に詳しくなった
+ Perl に詳しくなった
+ Java に詳しくなった
+ ハッシュのソートに詳しくなった

参照したサイト
*[Stream API を使用して Map をソートする](https://qiita.com/kakasak/items/1df7e6ee6f1ddfe79efb)*