【ハッシュメニュー】ハッシュテーブル(チェイン法) (paizaランク C)-解答例-PHP編

2022年7月21日

【ハッシュメニュー】> 【ハッシュテーブルを使おう】STEP: 2 ハッシュテーブル(チェイン法) (paizaランク C 相当) [難易度: 1512 ±40]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

n 個の整数 x_1, x_2, ..., x_n が順に与えられます。ハッシュ関数 H(x) = x % 10 を用いて、この n 個の整数をハッシュテーブルに格納してください。ハッシュテーブルは要素数 10 の配列とし、配列の各要素にはデータのリストを格納することとします。なお、各要素の初期値は空リストとします。各リストには複数のデータが含まれる可能性がありますが、格納した順番にデータが並ぶように実装してください。最後に、ハッシュテーブルの状態を出力してください。

入力例 1 を用いて説明します。
最初に格納するデータは 17 です。このデータのハッシュ値は 17 % 10 = 7 ですから、配列の添字 7 の位置にあるリストにデータ 17 を格納します。リストは [17] となります。
次に格納するデータは 188 で、ハッシュ値は 8 となるので、添字 8 の位置にあるリストにデータ 188 を格納します。リストは [188] となります。
次に格納するデータは 38 で、ハッシュ値は 8 となるので、添字 8 の位置にあるリストにデータ 38 を格納します。リストは [188, 38] となります。
次に格納するデータは 77777 で、ハッシュ値は 7 となるので、添字 7 の位置にあるリストにデータ 77777 を格納します。リストは [17, 77777] となります。

以上で全データの格納が終了しました。最終的なハッシュテーブルの状態は、

[]
[]
[]
[]
[]
[]
[]
[17, 77777]
[188, 38]
[]

となります。

入力値（例）
4
17
188
38
77777

出力値（例）

17 77777
188 38

解答例

<?php
    for ($i = 0; $i < 10; $i++) {
        $a[$i] = [];
    }
    
    $n = trim(fgets(STDIN));
    for ($i = 0; $i < $n; $i++) {
        $x = trim(fgets(STDIN));
        
        $hash = $x % 10;
        
        array_push($a[$hash], $x);
    }
    //print_r($a);
    
    for ($i = 0; $i < 10; $i++) {
        
        if (empty($a[$i])) {
            echo "\n";
            
        } else {
            echo implode(" ", $a[$i]). "\n";
        }
    }
?>

<?php

for ($i = 0; $i < 10; $i++) {

$a[$i] = [];

}

$n = trim(fgets(STDIN));

for ($i = 0; $i < $n; $i++) {

$x = trim(fgets(STDIN));

$hash = $x % 10;

array_push($a[$hash], $x);

}

//print_r($a);

for ($i = 0; $i < 10; $i++) {

if (empty($a[$i])) {

echo "\n";

} else {

echo implode(" ", $a[$i]). "\n";

}

解答例

カテゴリー