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

※この問題は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}

試したこと

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

m.ts10806

2020/08/19 08:04

＞（paizaラーニングの問題集なので質問は許可されています）これをタイトルに書く必要はないのでは。あくまで要件を記載してください。 https://teratail.com/help/question-tips#questionTips3-1

nogish

2020/08/19 08:09

ご指摘ありがとうございます質問へのご回答お待ちしております

dodox86

2020/08/19 08:21

質問文に挙げられた問題文だけでは、どのような入力データで、どのような出力データが求められているかいまいち判然としませんね。例えば入力データとしては n りんごの数1 バナナの数1 りんごの数2 バナナの数2 .... りんごの数n バナナの数n っぽいのか。（問題文と、ご提示のコードを照らし合わせてみても違う気がしますが）

dodox86

2020/08/19 10:28 編集

先の私のコメントが質問者さんに伝わっていなかったかもしれませんので一応補足ですが、要は、問題文があいまいなので、入力データと出力データの形式と、Paizaのような競技プログラミング系の問題でよくある実例の入力データ、出力データが分からないと第三者である回答者には恐らく検証も、答えようも無い、と言うことです。例えば「各ペアの最初の数はりんごの個数を、その次の数はバナナの個数を表している」とありますが、条件に「ふたつのペアのりんごの数が異なる場合、」とあり、その「ふたつのペア」とは1行内に収まったデータなのか、複数行にまたがったデータなのか、それともまた違うものなのか、文だけでは分かりません。質問者さんご提示のPaizaラーニングのURLも、練習問題がたくさんあるように見え、どれを指しているかも分かりません。

nogish

2020/08/19 14:11

不十分な質問で大変申し訳ありません。すぐに編集します

行動規範の内容に同意します

回答2件

ベストアンサー

ひとつの考え方、ヒントとして回答とします。下記の条件1ですが、

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

これは、(リンゴの数, バナナの数)として (10, 1)と(11, 1)のふたつのペアがあった場合、(11, 1)のペアの方がリンゴの数が多いので、(11, 1)のペアが偉いです。加えて、「バナナの数は関係ない」と言う条件を当てはめて考えると(10, 10)と(11, 1)のふたつのペアではバナナの数は関係ないので、依然として(11, 1)が偉いです。

下記の条件2ですが、

りんごの数が同じである場合、バナナの数が多い方が偉い。

これは、(10, 1)と(10, 2)のふたつのペアでは、バナナの数が多い(10, 2)の方が偉いということになります。
ですので、

の入力データは、以下のような出力になるのが期待されるはずです。（それで正しいですよね？）

さて、これをこのような順にするにはどうしたら良いかですが、りんごの数とバナナの数を桁数を合わせた数字の文字列にすると、それで自然と辞書順の並びで考えることができるようになります。りんごの数を100と1000の位、バナナの数を1と10の位に配置させると考えてみても良いでしょうか。

10 1    → "1001"
11 1    → "1101"
10 10   → "1010"
10 2    → "1002"

これらの文字列を辞書の降順（逆順）にソートすると、自然に問題で言うところの「偉い順」になります。

"1101"
"1010"
"1002"
"1001"

桁数は数値の取り得る範囲を意識しなければなりませんし、期待する出力としては元の入力データのようなペアの表記にしなければなりませんが、問題の捉え方としては上記のようなものでも回答が可能、と言うことです。「数値の組み合わせで辞書式でソート」とは、このようなことを言っているのだと思われます。

投稿2020/08/19 15:12

dodox86

総合スコア9183

dodox86

2020/08/19 15:27

桁数を合わせた文字列を例に書きましたが、文字列に限らず、整数でもOKかもしれませんね。リンゴの数を上位桁に持っていくようなかたちです。例えば（比較のペア値 = リンゴの数 * 100 + バナナの数）とか。あくまでヒントなので、問題の全貌を考慮し、必要に応じて修正してください。

nogish

2020/08/20 13:19

とてもわかりやすいヒントありがとうございます！おかげで正解までたどり着けることができました。整数を文字列で辞書式にするという発想に驚きました。恥ずかしながら、質問文のコードでString型でソートしていたのは、半ばやけくそでString型を使っていただけなので、、やっと整数と辞書式の関係をなんとなく理解できた気がします整数型のバージョンも面白そうなのでやってみます。本当にわかりやすく助かりました。ありがとうございました！

行動規範の内容に同意します