辞書式ソート（数値の組み合わせを降順にソート）

Question

※この問題はpaizaの問題ですが、paizaラーニングの問題集のため、質問は自由とされています
（URL: https://paiza.jp/works/mondai）

なお、このコーナー内の問題については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
授業や研修にもご利用いただけますので、ぜひ教材などにもお使いください。

ぜひご回答お願いいたします。

前提・実現したいこと

問題：
正整数 n が与えられ、数のペアが n 個与えられます。各ペアの最初の数はりんごの個数（a）を、その次の数はバナナ（b）の個数を表しています。これらの数のペアを以下の規則に従って、偉い順に並び替えてください。

1. ふたつのペアのりんごの数が異なる場合、りんごの数が多い方が偉い（この際、バナナの数は関係ない）。
2. りんごの数が同じである場合、バナナの数が多い方が偉い。

入力：
n
a_1 b_1
...
a_n b_n
（a:りんごの数、b:バナナの数）

期待する出力：
ペアを偉い順に並べ替え、改行区切りで n 行、順に出力してください。出力の各行は入力と同じく、 "a_i b_i" のように、りんごの個数とバナナの数が、この順に、半角スペースで区切られているものとします。
末尾に改行を入れ、余計な文字、空行を含んではいけません。

発生している問題・エラーメッセージ

たくさん調べてみたのですが、この辞書式ソートが全くわかりません
解答例、もしくはヒントを教えていただきたいです、、

該当のソースコード

Java
1import java.util.*;
2
3
4public class Main {
5    public static void main(String[] args) {
6        Scanner sc = new Scanner(System.in);
7        // n個のりんごとバナナの数のペア
8        int n = Integer.parseInt(sc.nextLine());
9        ArrayList<String> ab = new ArrayList<String>();
10        for (int i = 0; i < n; i++) {
11            ab.add(sc.nextLine());
12        }
13        // 並べ替え
14        Collections.sort(ab);
15        Collections.reverse(ab);
16        for (int i = 0; i < n; i++) {
17            System.out.println(ab.get(i));
18        }
19    }
20}

試したこと

二次元配列や二次元リストにしてみたり、辞書式ソートの基本も知らないので、学んでみたりもしたのですが、結局何も進歩しませんでした。

Accepted Answer

ひとつの考え方、ヒントとして回答とします。下記の条件1ですが、

> 1. ふたつのペアのりんごの数が異なる場合、りんごの数が多い方が偉い（この際、バナナの数は関係ない）。

これは、`(リンゴの数, バナナの数)`として `(10, 1)`と`(11, 1)`のふたつのペアがあった場合、`(11, 1)`のペアの方がリンゴの数が多いので、`(11, 1)`のペアが偉いです。加えて、「バナナの数は関係ない」と言う条件を当てはめて考えると`(10, 10)`と`(11, 1)`のふたつのペアではバナナの数は関係ないので、依然として`(11, 1)`が偉いです。

下記の条件2ですが、
> 2. りんごの数が同じである場合、バナナの数が多い方が偉い。

これは、`(10, 1)`と`(10, 2)`のふたつのペアでは、バナナの数が多い`(10, 2)`の方が偉いということになります。
ですので、
```Plain
4
10 1
11 1
10 10
10 2
```
の入力データは、以下のような出力になるのが期待されるはずです。（それで正しいですよね？）
```Plain
11 1
10 10
10 2
10 1
```

さて、これをこのような順にするにはどうしたら良いかですが、りんごの数とバナナの数を桁数を合わせた数字の文字列にすると、それで自然と辞書順の並びで考えることができるようになります。りんごの数を100と1000の位、バナナの数を1と10の位に配置させると考えてみても良いでしょうか。

```
10 1    → "1001"
11 1    → "1101"
10 10   → "1010"
10 2    → "1002"
```
これらの文字列を辞書の降順（逆順）にソートすると、自然に問題で言うところの「偉い順」になります。
```
"1101"
"1010"
"1002"
"1001"
```
桁数は数値の取り得る範囲を意識しなければなりませんし、期待する出力としては元の入力データのようなペアの表記にしなければなりませんが、問題の捉え方としては上記のようなものでも回答が可能、と言うことです。「数値の組み合わせで辞書式でソート」とは、このようなことを言っているのだと思われます。

Answer

まず、普通のソートができますか？「辞書式」というのは、順序付けのルールの決め方の手法にすぎません。

<Java>辞書式ソート（数値の組み合わせを降順にソート）

前提・実現したいこと

発生している問題・エラーメッセージ

該当のソースコード

試したこと

関連した質問