科目Bの併合（マージ）問題の解き方｜2つの配列を合わせる手順を追う

i と j が交互に増えていくうちに、どっちを進めたのか分からなくなる。

科目Bの問題で、2つの配列を見比べながら値を1つずつ取り出すコードに出会って、途中で手が止まったことはありませんか？

1つの配列を前から順に読むのはできるのに、配列が2つになると急に難しく感じる。そんな人は多いのではないでしょうか。

大丈夫です。併合の問題で必要なのは、2本の指を2つの配列の先頭に置き、小さいほうを1つずつ動かしていく、という手順だけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、時刻順に並んだ2つのログファイルを、1本の時系列にまとめる処理を何度も書いています。

そのときに使うのが、まさにこの記事で扱う併合の考え方です。並んでいるもの同士を合わせる場面は、試験の外でも意外なほど多くあります。

この記事では、併合の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中で、こうした問題がどこに位置するのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

併合（マージ）の問題は何を聞いているのか¶

最初に、併合とは何かを短く押さえておきましょう。何のための処理なのかが分かると、コードの意図がぐっと読みやすくなります。

併合とは、それぞれ小さい順に並んでいる2つの配列を、並び順を保ったまま1つの配列にまとめる処理のことです。まとめたあとで並べ替えるのではなく、まとめながら順番をそろえていく点に特徴があります。

試験で問われるのは、ある2つの配列を渡したときに、できあがる配列がどうなるかです。あるいは、正しくまとめられるように、空欄へどの条件や式を入れるかが問われます。

併合が使われる場面¶

併合は、それ単体でも出題されますが、別のアルゴリズムの部品としても登場します。どんな場面で使われるのかを知っておくと、見慣れないコードの中に併合が隠れていても気付けるようになります。

代表的な場面を表にまとめました。

どの場面でも、中身の手順は同じです。この記事の例題で追い方を身に付ければ、題材が変わっても同じように読めます。

まず目を付ける場所¶

併合とは何かがつかめたら、次はコードのどこから読むかを決めます。併合の問題では、目を付ける場所が3つあります。

ひとつ目は2本の添字、ふたつ目は値を比べている if の行、みっつ目は最初のループのあとに続く残りの処理です。この順番で見ていくと、コードの役割がはっきりします。

添字が2本あることを確かめる¶

最初に見るのは、配列ごとに用意された添字です。一方の配列を i で、もう一方を j で指している、というように、2本の添字が別々に動きます。

ここで大事なのは、1回のループで進むのはどちらか片方だけ、という点です。両方が同時に進むことはありません。

小さいほうの値を結果に入れたら、その値を指していた添字だけを1つ進めます。この決まりを先に頭に入れておくと、トレースが一気に楽になります。

最初のループのあとを必ず見る¶

次に見るのは、2つの配列を比べるループが終わったあとの処理です。比べるループは、どちらかの配列を使い切った時点で終わります。

つまり、もう一方の配列には、まだ値が残っている可能性があります。その残りを結果の末尾に足す処理がなければ、値が欠けてしまいます。

残りを足すループは、空欄補充でよく狙われる場所です。コードを読むときは、比べるループの下に何が書かれているかを必ず確かめましょう。

例題：2つの配列を1つにまとめる¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のコードは、小さい順に並んだ2つの整数型の配列 a と b を受け取り、併合した配列を返す関数です。

○整数型の配列: merge(整数型の配列: a, 整数型の配列: b)
  整数型の配列: result ← {}
  整数型: i ← 1
  整数型: j ← 1
  while ((i ≦ aの要素数) and (j ≦ bの要素数))
    if (a[i] ≦ b[j])
      resultの末尾に a[i] の値を追加する
      i ← i + 1
    else
      resultの末尾に b[j] の値を追加する
      j ← j + 1
    endif
  endwhile
  while (i ≦ aの要素数)
    resultの末尾に a[i] の値を追加する
    i ← i + 1
  endwhile
  while (j ≦ bの要素数)
    resultの末尾に b[j] の値を追加する
    j ← j + 1
  endwhile
  return result

最初の while で a[i] と b[j] を比べ、小さいほうを result の末尾に追加します。どちらかを使い切ったら、残っている側の値を、2つ目か3つ目の while でまとめて追加します。

では、a に {2, 5, 8}、b に {3, 4, 9, 10} を渡すと、戻り値はどんな配列になるでしょうか？

トレース表で2本の添字を追う¶

頭の中だけで比べていると、どちらの添字を進めたのかが分からなくなりがちです。そこで、ループ1回ごとの i と j、比べた値、追加した値をトレース表に書きます。

ポイントは、添字だけでなく、そのとき指している値も一緒に書くことです。a[i] と b[j] を並べて書けば、どちらが小さいかが一目で分かります。

5回目のあと i は 4 になり、a の要素数 3 を超えます。and でつながった条件の片方が偽になるので、最初の while を抜けます。

残りの値を足す¶

最初の while を抜けた時点で、i は 4、j は 3 です。a はもう使い切っているので、2つ目の while は一度も実行されません。

3つ目の while では、b に残っている 9 と 10 を順に追加します。j が 5 になったところで条件が偽になり、ループを抜けます。

戻り値は {2, 3, 4, 5, 8, 9, 10} です。元の2つの配列の要素数を足すと 3 ＋ 4 ＝ 7 で、結果の要素数も 7 になっています。

最後に要素数を足し算で確かめる習慣を付けておくと、残りの処理の書き忘れや読み落としにすぐ気付けます。トレース表を書く作業そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

比べる回数はどれくらいか¶

併合では、1回比べるたびに必ず1つの値が結果に入ります。そのため、比べる回数は、2つの配列の要素数の合計を超えることはありません。

いったん全体を並べ替えるよりも、ずっと少ない手間でまとめられるのが併合の強みです。マージソートが速い理由も、この性質にあります。

整列のアルゴリズムで値がどう動くのかを、別の角度から確かめたい場合は、こちらの記事も参考になります。

【関連記事】科目Bのソート問題を解くコツ｜交換される値を追ってみよう

間違いやすい選択肢の見分け方¶

併合の問題では、比較の記号やループの条件を少しだけ変えた選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

よくある誤りを表にまとめました。

この中でも、特によく狙われるのがループ条件の and と or、そして等しい値の扱いです。順番に見ていきましょう。

and でつなぐ理由¶

最初の while は、両方の配列にまだ値が残っている間だけ続ける必要があります。だから、2つの条件を and でつなぎます。

もし or にすると、片方を使い切っても比べるループが続きます。使い切った配列の要素数を超えた位置を読もうとして、正しく動かなくなります。

選択肢で迷ったら、片方の配列が先に空になる場面を想像してみてください。そのときにループが止まるかどうかで、and と or は見分けられます。

等しい値はどちらから入れるか¶

a[i] ≦ b[j] と a[i] < b[j] は、ほとんどの場面で同じ結果になります。違いが出るのは、a[i] と b[j] が等しいときだけです。

≦ なら a の値が先に、< なら b の値が先に入ります。整数を並べるだけなら結果は変わりませんが、名前と点数を組にしたデータでは、同じ点数の人の並び順が変わります。

元の並び順を保ちたいなら、先にある a の値を優先する ≦ を使います。問題文に、等しい場合の扱いが書かれていないかを必ず確かめましょう。

添字を1つずらすだけで答えが変わる¶

併合のコードは、添字を1つ間違えるだけで、値が重複したり欠けたりします。そして、そのずれはトレース表を書かなければ気付きにくいものです。

添字の追い方や、配列の範囲の考え方に不安がある場合は、こちらの記事で先に整理しておくと安心です。

【関連記事】科目Bの配列問題の解き方｜添字を表にして追う方法

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。2本の添字が交互に進むような処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの回で予想とずれたのかがすぐに分かります。

試すときは、渡す配列を変えてみるのがおすすめです。a を {1, 2, 3}、b を {4, 5, 6} のように片方が先に尽きる組み合わせにしたり、a と b に同じ値を混ぜたりして、結果を予想してから動かしてみてください。

最初の while の条件を or に書き換えて、どこでおかしくなるのかを確かめてみるのも良い練習です。間違った選択肢を自分の手で動かすと、なぜそれが誤りなのかが体で分かります。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、2本の添字が1つずつ進んでいく様子を確かめてみてください。

まとめ¶

科目Bの併合の問題は、難しいアルゴリズムの知識を問うものではありません。2本の添字と、そのとき指している値をトレース表に書いていけば必ず解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、要素が3つと4つくらいの短い配列で十分です。小さいほうを1つ入れては添字を進める練習を繰り返すうちに、併合のコードを見ただけで、2本の指が動く様子が思い浮かぶようになります。

並んでいるもの同士を合わせる考え方は、試験の後も長く使える力です。次に2つの配列が出てくる問題に出会ったら、まずは両方の先頭に指を置くところから始めてみてください。