科目Bの集合演算問題の解き方｜和集合・積集合を配列で追う

共通の値を取り出すだけなのに、どっちの配列を回しているのか分からなくなる。

科目Bの問題で、2つの配列を突き合わせるコードを見て、手が止まったことはありませんか？

配列が2つ、ループも2つ、そこに論理型の変数まで出てくる。どれが何の役なのかが見えなくなってしまう人も多いのではないでしょうか。

大丈夫です。集合演算の問題は、片方の配列の値を1つずつ取り出して、もう片方にあるかどうかを確かめているだけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、2つのシステムの会員IDを突き合わせて、片方にしか登録されていない会員を洗い出す作業を何度も担当してきました。

ある時は、抽出した件数が想定より多く、調べてみると比べる向きが逆になっていました。小さなデータで、どの値がどちらの結果に入るのかを表に書き出したことで、ようやく原因に気づけました。

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

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

集合演算の問題は何を聞いているのか¶

最初に、集合演算とはどういう処理なのかを短く押さえておきましょう。集合とは、同じ値を重ねて持たない、値の集まりのことです。

科目Bでは、集合を配列で表すことがよくあります。配列の中に同じ値が二度出てこない、という前提で2つの配列を比べ、条件に合う値だけを新しい配列に集める処理が、集合演算の問題の正体です。

身近な例で考えてみましょう。英語クラブの名簿と、数学クラブの名簿があるとします。

両方に入っている人を探す、どちらかに入っている人を全員書き出す、英語クラブだけの人を探す。この3つの作業が、そのまま集合演算になります。

3つの演算を表で比べる¶

集合演算にはいくつか種類がありますが、科目Bでまず押さえたいのは3つです。名前と中身を、名簿の例と合わせて表に整理しました。

表の右端を見比べてください。積集合と差集合は、見つかったか見つからなかったかが逆になっているだけです。

この関係は、あとで選択肢を見分けるときに大きな手がかりになります。条件を1か所反対にすると、積集合のつもりが差集合になってしまうのです。

併合や重複除去の問題との違い¶

集合演算とよく似た問題に、2つの配列を1つにまとめる併合の問題があります。併合は、小さい順に並んだ2つの配列を、順番を保ったまま1本にする処理です。

集合演算は、並び順を前提にしないことが多く、値があるかないかだけに注目します。並んだ配列どうしを前から比べていく形は、併合の記事で詳しく扱っています。

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

また、1つの配列の中から同じ値を取り除く重複除去も、見つかったかどうかを確かめる点でよく似ています。違いは、比べる相手が自分で作っている結果の配列か、もう1つの配列か、という点です。

【関連記事】科目Bの重複を取り除く問題の解き方｜既に出た値かどうかを追う

まず目を付ける場所¶

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

ひとつ目は外側のループがどちらの配列を回しているか、ふたつ目は論理型の変数を戻している位置、みっつ目は結果に追加する条件です。この3か所を確かめれば、どの演算をしているのかが分かります。

外側のループはどちらの配列か¶

最初に確かめたいのが、外側のループの終わりが a の要素数なのか、b の要素数なのかです。外側で回している配列が、結果に入れる値の出どころになります。

差集合では、この向きが答えを大きく変えます。a − b と b − a はまったく別の結果になるので、外側の配列の名前を必ず確かめましょう。

論理型の変数はどこで戻しているか¶

次に見るのが、found のような論理型の変数を false に戻している行の位置です。この行は、外側のループの中、内側のループの手前にあるのが正しい形です。

found は、今取り出した1つの値が、もう片方の配列にあったかどうかを覚えておく変数です。値が変わるたびに、見つかっていない状態から確かめ直す必要があります。

見つかったかどうかを覚えておく変数の読み方そのものに不安がある場合は、こちらの記事が参考になります。

【関連記事】擬似言語のフラグ変数（論理型）の使い方とは？見つかったかどうかを覚えておく処理を解説

追加するのはどちらのときか¶

最後に見るのが、結果に値を追加する行の条件です。found が true のときに追加していれば積集合、false のときに追加していれば差集合です。

和集合は少し形が違います。先に a をまるごと結果に入れておき、そのあと b の値のうち a に見つからなかったものだけを足していきます。

例題：2つの配列の共通部分を求める¶

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

次のプログラムは、整数型の配列 a と b を受け取り、両方に含まれる値を a に現れた順に並べた配列を返す関数です。a と b はそれぞれ、同じ値を二度含まないものとします。配列の添字は1から始まります。

○整数型の配列: intersection(整数型の配列: a, 整数型の配列: b)
  整数型の配列: result ← {}
  整数型: i, j
  論理型: found
  for (i を 1 から a の要素数 まで 1 ずつ増やす)
    found ← false
    for (j を 1 から b の要素数 まで 1 ずつ増やす)
      if (a[i] が b[j] と等しい)
        found ← true
      endif
    endfor
    if (found が true と等しい)
      result の末尾 に a[i] の値 を追加する
    endif
  endfor
  return result

intersection は、a から値を1つ取り出すたびに found を false に戻します。そのあと b を先頭から最後まで見て、同じ値があれば found を true にします。

最後に、found が true なら、その値は両方にあるので result の末尾に加えます。では、intersection({2, 5, 7, 9}, {5, 1, 9, 4}) の戻り値は何になるでしょうか？

トレース表で結果の配列を追う¶

頭の中だけで二重のループを追うと、どの値がどちらの配列にあったのかが分からなくなりがちです。そこで、外側のループ1回ごとに、取り出した値、b の中で一致した位置、found、追加後の result をトレース表に書きます。

ポイントは、一致した位置を j の値で書いておくことです。見つからなかったときは、なしと書きます。

できあがった result は {5, 9} です。b の並びは {5, 1, 9, 4} ですが、結果は a に現れた順になっている点にも注目してください。

外側で回している配列の順番が、そのまま結果の順番になります。並び順を聞かれたときは、外側の配列を見れば迷いません。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

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

同じ例で和集合と差集合も求める¶

同じ a と b を使って、残りの2つの演算も確かめておきましょう。差集合 a − b は、上のトレース表で found が false だった行の値を集めたものです。

つまり {2, 7} になります。表を1枚書いておけば、積集合と差集合は同時に読み取れるわけです。

和集合は、まず a の {2, 5, 7, 9} を結果に入れます。次に b を1つずつ見て、a に無い 1 と 4 だけを足すので、結果は {2, 5, 7, 9, 1, 4} です。

3つの結果を並べると、次のようになります。

和集合の要素数は、a の要素数と b の要素数を足して、積集合の要素数を引いた数になります。4 + 4 − 2 で6です。

この関係を覚えておくと、要素数だけを聞かれたときの検算に使えます。

値を添字にした論理型の配列で表す¶

科目Bでは、集合を別の形で表すこともあります。値の範囲が1から10のように小さい整数に決まっているとき、その値があるかどうかを論理型の配列で持つ方法です。

たとえば inA[k] が true なら k は a に含まれる、という意味になります。この形だと、3つの演算はループ1つで書けます。

for (k を 1 から 10 まで 1 ずつ増やす)
  inUnion[k] ← inA[k] or inB[k]
  inInter[k] ← inA[k] and inB[k]
  inDiff[k] ← inA[k] and (not inB[k])
endfor

和集合は or、積集合は and、差集合は and と not の組み合わせです。二重のループで探していた処理が、添字ごとの論理演算に置き換わっています。

この考え方を1つの整数のビットに詰めたものが、ビット演算で集合を表す問題です。論理積やシフトの追い方は、こちらの記事で詳しく扱っています。

【関連記事】科目Bのビット演算問題の解き方｜論理積とシフトを2進数で追う

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

集合演算の問題では、条件や初期化の位置を少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の intersection({2, 5, 7, 9}, {5, 1, 9, 4}) を使って、よくある誤りを表にまとめました。

条件を反対にした選択肢は、実は差集合として正しく動きます。だからこそ、設問がどの演算を求めているかを、最初に言葉で確かめておくことが大切です。

見つからない値が後半に来る例で試す¶

初期化の位置で迷ったら、見つかる値のあとに見つからない値が来る例を作ってみてください。例題の a は、5 が見つかったあとに、b に無い 7 が来る形になっています。

found を外側のループの前で1回だけ false にすると、i が2のときに true になったまま戻りません。そのため、i が3で b に無い 7 が来ても、見つかった扱いになって追加されてしまうのです。

一方で、共通の値が最後にしか無い例だと、誤った書き方でも正しい答えが出ることがあります。答えが合ったから正しい、と決めつけず、順番を変えた例でも試すのが確実です。

差集合は向きを言葉にする¶

差集合の問題では、a − b なのか b − a なのかを、必ず言葉にして確かめましょう。a にあって b に無いもの、と口に出すだけで、外側で回すべき配列がはっきりします。

冒頭でお話しした会員IDの突き合わせでも、原因はこの向きでした。片方のシステムにしかいない会員を出すはずが、逆の向きで抽出していたため、件数が大きくずれていたのです。

和集合は二度入れていないかを見る¶

和集合の選択肢では、共通の値が二度入っていないかを確かめます。結果の要素数が、2つの配列の要素数の合計と同じになっていたら、確認の処理が抜けている合図です。

先ほどの、要素数の合計から積集合の要素数を引く関係を使えば、すぐに検算できます。

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

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。2つの配列を行き来する処理ほど、動かして見る効果は大きくなります。

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

試すときは、まず正しい intersection を動かして、result が {5, 9} になるのを確かめてください。そのあと、追加する条件を false に変えて、結果が {2, 7} の差集合に変わる様子を見ると、条件1つで演算が入れ替わることが体で分かります。

慣れてきたら、found ← false の行を外側のループの前に移したり、和集合を自分で書いてみたりしましょう。どの値がいつ結果に入るのかが、少しずつ見えてくるはずです。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、2つの配列を突き合わせて結果が1つずつ伸びていく様子を確かめてみてください。

まとめ¶

科目Bの集合演算の問題は、数学の難しい知識を問うものではありません。片方の値を1つずつ取り出し、もう片方にあるかを確かめて、条件に合えば加える、という手順を表に書いて追えば、落ち着いて解けます。

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

最初は、要素が4個前後の小さな配列で十分です。何度か表を書くうちに、追加する条件を見ただけで、積集合か差集合かが分かるようになります。

外側で回す配列が結果の出どころ。true で追加なら積集合、false で追加なら差集合。 この2つを習慣にしておけば、集合演算の問題にも自信を持って向き合えます。次に2つの配列を突き合わせるコードに出会ったら、まずは a の先頭の値が b にあるかどうかから表に書いてみてください。