はじめに

アルゴリズムの基礎を学ぶため、現在Paizaラーニングの問題集に取り組んでいます。こちらのリンク先の問題はCランク(forループなどの基礎的な問題が解ける程度の水準)達成に向けた問題集ですので基本的に難易度は低いはずですが、躓いた問題があったので投稿しておきます。

ソート問題 STEP:3 辞書式ソート

難易度は堂々のDランクです。ぐぬぬ。
PHPではソート用の関数としてsort()やrsort()といった関数が用意されていますが、文字列の場合でもこれが適用できますよ、ということを初学者向けに紹介するというのがコンセプトとなった問題な気がします。気がするのですが・・・

問題概要

こちらから。
https://paiza.jp/works/mondai/c_rank_level_up_problems/c_rank_sort_step3?language_uid=php
ユーザー登録が必要ですが、問題は無料でチャレンジすることができます。

----入力例----
3
1 3
3 5
3 4

----出力例----
3 5
3 4
1 3

ざっくり問題を紹介しますと、まずはじめの入力値として整数nが与えられ、スペースで区切られたペアの数字列(a_b)が入力値分n個与えられます。

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

上記の条件を踏まえて、偉い順にソートして値を出力しましょうという問題です。

解いてみる

はじめに下記のようなコードで入力サンプルをクリア。

<?php
    //出力をループする回数
    $input_line = fgets(STDIN);
    
    //残り入力される分だけ配列$array[]に入れる
    while ($input = fgets(STDIN)) {
        $array[] = trim($input);
    }

    //関数で大きい順(降順)にソートする
    rsort($array);
    
    //改行して値を出力
    for ($i=0; $i < $input_line; $i++) {
        echo $array[$i]."\n";
    }
    
?>

----入力値----
3
3 5
1 3
3 4

----出力値----
3 5
3 4
1 3

しかしこのコードでは、以下のような入力の場合に上手くソートされておらずNG判定となりました。

----入力値----
7
10 5
1 3
2 1
20 10
3 4
20 1
20 5

----出力値----
3 4
20 5
20 10
20 1
2 1
10 5
1 3

入力した値に半角スペースが含まれているため文字列として格納されていますので、数字の3と20を比較した時に、初めの3と2が比較され、3の方が高い値であるとみなされてしまっています。

paiza公式(Python3の場合)の解説を見ると、「入力値を保持した配列をそのままソート関数に渡して降順に並べるだけで良い」と記載があります。PHPの解法は載っていなかったため別言語の解法を確認したのですが、あまり上手くいかず。どうしたものか・・・

1時間くらい悩みましたが、以下のステップを踏むことで解決しました。

1.入力値を配列に格納する
2.explode()関数で値を分割する
3.配列の値をsprintf()関数を用いて、書式を整える(1という値を01表記にする)
4.rsort()関数でソート(書式を整えて03とした値なら20と比較した場合でもソートできるはず)
5.explode()で再分割。sprintf()関数で元の書式に戻してやり、改めて配列に格納
6.整えた配列を出力

sprintf関数については、個人的にこちらのページが分かりやすかったです。
https://wp.tech-style.info/archives/582

最終的に以下のコードとなりました。


<?php

$inputNum = trim(fgets(STDIN));

//1.入力値を配列に格納する
while ($input = fgets(STDIN)) {
    $array[] = trim($input);
}

for ($i=0; $i<$inputNum; $i++) {
    //2.explode()関数で値を分割する
    $test = explode(" ", $array[$i]); 

    //3.配列の値をsprintf()関数を用いて、書式を整える(1という値を01表記にする)
    $test[0] = sprintf('%02d', $test[0]);
    $test[1] = sprintf('%02d', $test[1]);
    $sort_array[] = $test[0] . " " . $test[1];
}

//4.rsort()関数でソート
rsort($sort_array);

for ($i=0; $i<$inputNum; $i++) {
    //5.explodeで再分割。sprintfで元の書式に戻してやり、改めて配列に格納
    $answer = explode(" ", $sort_array[$i]);
    $answer[0] = sprintf('%01d', $answer[0]);
    $answer[1] = sprintf('%01d', $answer[1]);
    $answer_array[] = $answer[0] . " " . $answer[1];
}

//6.整えた配列を出力
for ($i=0; $i < $inputNum; $i++) {
    echo $answer_array[$i] . "\n";
}
    
?>

無事出力できました。

----入力値----
7
10 5
1 3
2 1
20 10
3 4
20 1
20 5

----出力値----
20 10
20 5
20 1
10 5
3 4
2 1
1 3

おわりに

冗長なコードである感じもありますが、備忘録も兼ねて記載させて頂きました。
まだまだ勉強不足ですので、PHPでももっと楽に出力させられるよ、こんな考え方でもソートできるよ、などの意見がありましたらご教示いただければとても嬉しいです。

閲覧ありがとうございました！