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

同じ値を取り除くだけなのに、なぜループが二重になっているの？

科目Bの問題で、配列から重複した値を取り除くコードを見て、どこから読めばいいのか迷ったことはありませんか？

やりたいことは単純そうなのに、ループが2つあって、論理型の変数まで出てくる。そこで混乱してしまう人も多いのではないでしょうか。

大丈夫です。重複を取り除く処理は、新しく来た値が、もう結果に入っているかどうかを確かめているだけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、CSV ファイルから会員データを取り込むときに、同じメールアドレスが二重に登録されてしまう不具合を直したことがあります。

原因は、すでに取り込んだデータと比べる処理が、ある条件のときだけ飛ばされていたことでした。小さなデータで、どの値がいつ結果に入ったのかを表に書き出したことで、ようやく原因が見えてきました。

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

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

重複を取り除く問題は何を聞いているのか¶

最初に、重複を取り除くとはどういう処理なのかを短く押さえておきましょう。言葉にすると、同じ値が2回以上出てきたら、2回目以降を捨てることです。

重複除去とは、配列の値を先頭から順に見て、まだ結果に入っていない値だけを結果に加えていく処理のことです。最初に現れた順番はそのまま残るので、結果の並び方にも意味があります。

身近な例で考えてみましょう。出席カードを集めたら、同じ人が2枚出していた。名簿を作るときは、名前を1枚ずつ確かめて、まだ書いていない人だけを書き足していくはずです。

コンピュータも同じ手順を踏みます。ただし、すでに書いた名前を一度に見渡せないので、名簿を先頭から1人ずつ見直して、同じ名前がないかを確かめます。

この見直しの部分が、内側のループの正体です。二重のループに見えても、外側は配列の値を1つずつ取り出す役、内側は名簿を見直す役と分けて考えれば、怖くありません。

科目Bで問われる形¶

試験の擬似言語で重複除去が出るときは、考え方そのものより、比べる相手や変数の初期化の位置が問われます。どんな形で聞かれやすいのかを、表に整理しました。

どの形でも、中心にあるのは、何と比べているかと、論理型の変数をいつ戻しているかの2つです。この2つを小さな例で確かめられれば、問われ方が変わっても同じ手順で解けます。

出現回数を数える問題との違い¶

重複除去とよく似た問題に、値ごとの出現回数を数える問題があります。2つはゴールが違います。

出現回数の問題は、値ごとに何回出たかという数を答えにします。重複除去の問題は、値そのものを1回ずつ並べた配列を答えにします。

値を添字として使う数え方については、こちらの記事で詳しく扱っています。後半で紹介する別の解き方にもつながるので、あわせて読んでおくと理解が深まります。

【関連記事】科目Bの出現回数を数える問題の解き方｜カウント用の配列を追う

まず目を付ける場所¶

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

ひとつ目は内側のループで比べている相手、ふたつ目は論理型の変数を戻している位置、みっつ目は結果に追加する条件です。この3か所が分かれば、ずれた選択肢をほぼ見抜けます。

内側のループは何と比べているか¶

最初に確かめたいのが、内側のループがどの配列を見ているかです。多くの問題では、結果の配列を先頭から見直して、今の値と同じものがないかを探しています。

ここで、結果の配列ではなく元の配列の手前の部分と比べる書き方もあります。どちらも重複を見つけられますが、ループの範囲の書き方が変わるので、配列の名前を必ず確かめましょう。

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

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

なぜ外側のループの中で戻す必要があるのでしょうか？ found は、今取り出した1つの値が結果にあるかどうかを覚えておく変数だからです。

前の値で true になったまま次の値に進むと、新しい値なのに見つかった扱いになってしまいます。値が変わるたびに、見つかっていない状態から数え直す必要があるわけです。

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

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

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

最後に見るのが、結果に値を追加する行の条件です。追加してよいのは、結果の中に同じ値が見つからなかったとき、つまり found が false のときです。

条件が反対になっていると、すでにある値だけを追加しようとします。最初は結果が空なので何も見つからず、結局1つも追加されないまま終わってしまいます。

例題：配列から重複を取り除く¶

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

次のプログラムは、整数型の配列 data から重複した値を取り除き、最初に現れた順に並べた新しい配列を返す関数です。配列の添字は1から始まります。

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

removeDuplicates は、data から値を1つ取り出すたびに、found を false に戻します。そのあと、result を先頭から見直して、同じ値があれば found を true にします。

最後に、found が false のままなら、その値はまだ result にないので末尾に加えます。では、removeDuplicates({3, 1, 3, 2, 1}) の戻り値は何になるでしょうか？

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

頭の中だけで二重のループを追うと、result に何が入っているのかが分からなくなりがちです。そこで、外側のループ1回ごとに、取り出した値、比べる前の result、found、追加後の result をトレース表に書きます。

ポイントは、result の中身を毎回まるごと書き写すことです。こうしておくと、内側のループがどの値と比べたのかが一目で分かります。

最初の行に注目してください。result が空なので、内側のループは1回も回りません。

found は false のまま残るので、3 がそのまま追加されます。空の配列に対するループが0回で終わることは、つまずきやすい点なので覚えておきましょう。

できあがった result は {3, 1, 2} です。戻り値の配列はこれで、要素数を聞かれたら3と答えます。

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

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

並んでいる配列なら隣と比べるだけで済む¶

data が小さい順に並んでいることが分かっている場合は、もっと簡単な書き方ができます。同じ値は必ず隣り合っているので、1つ前の値と比べるだけで重複かどうかが分かるからです。

for (i を 1 から data の要素数 まで 1 ずつ増やす)
  if ((i が 1 と等しい) or (data[i] が data[i − 1] と等しくない))
    result の末尾 に data[i] の値 を追加する
  endif
endfor

i が1のときは比べる相手がいないので、無条件で追加しています。この条件がないと、data[0] という存在しない要素を見に行ってしまいます。

この形では、ループが一重になります。内側で result を見直す必要がないので、配列が長くなっても比べる回数がずっと少なく済みます。

3つの解き方を比べる¶

ここまでの2つに、出現回数の記事で扱った、値を添字にする方法を加えると、重複除去の解き方は大きく3つに分かれます。どの書き方が出ても慌てないように、特徴を表にまとめました。

試験では、どの書き方が出るかは問題によって変わります。まずは比べている相手が何かを確かめ、表のどれに当たるのかを見分けるところから始めましょう。

ループの形から処理の速さを見積もる考え方は、こちらの記事で詳しく扱っています。

【関連記事】科目Bの計算量問題の解き方｜ループの形からオーダーを判断する

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

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

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

正解の {3, 1, 2} に対して、{3, 1} のように一部だけ合っている選択肢が並ぶのがこの種の問題の特徴です。最初の数個だけ見て選ぶと、うっかり近い答えに飛びついてしまいます。

新しい値が後半に来る例で試す¶

初期化の位置で迷ったら、重複した値のあとに新しい値が来る例を作ってみてください。例題の data は、3 の重複のあとに新しい 2 が来る形になっています。

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

一方で、重複のない {1, 2, 3} のような入力だと、found が一度も true にならないので、誤った書き方でも正しい答えが出てしまいます。だからこそ、重複のあとに新しい値が来る例を自分で作って試すのが確実です。

最初の1回で条件を確かめる¶

追加する条件で迷ったら、i が1のときだけを考えましょう。result は空なので、found は必ず false のままです。

最初の値は必ず結果に入るはずなので、false のときに追加する書き方が正しいと分かります。true のときに追加する書き方だと、最初の値すら入らないので、すぐに誤りだと気づけます。

実務でも見直しの漏れで重複が残る¶

冒頭でお話しした会員データの取り込みでも、問題は見直しの範囲にありました。ファイルを分けて取り込んだとき、前のファイルで登録した分を比べる相手に含めていなかったのです。

1つのファイルだけで試していたあいだは、きちんと重複が取り除かれていました。2つのファイルにまたがる例を1つ足したことで、ようやく不具合が表に出ました。

試験でも実務でも、比べる相手の範囲は見落としやすい場所です。内側のループを見るときは、どの配列のどこからどこまでと比べているのかを、必ず言葉にして確かめる習慣をつけておきましょう。

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

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

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

試すときは、まず正しい removeDuplicates を動かして、result が {3, 1, 2} になるのを確かめてください。そのあと、found ← false の行を外側のループの前に移して、2 が追加されなくなる様子を見ると、初期化の位置の大切さが体で分かります。

慣れてきたら、小さい順に並べた配列で隣と比べる書き方を試したり、すべて同じ値の配列を入れてみたりしましょう。どの値がいつ結果に入るのかが、少しずつ見えてくるはずです。

二重のループで位置をずらしながら比べる処理は、文字列照合の問題ともよく似ています。あわせて読んでおくと、内側のループの読み方がさらに安定します。

【関連記事】科目Bの文字列照合問題の解き方｜照合する位置をずらして追う

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

まとめ¶

科目Bの重複を取り除く問題は、難しいアルゴリズムの知識を問うものではありません。新しい値が結果にすでにあるかを確かめ、無ければ加える、という手順を表に書いて追えば、落ち着いて解けます。

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

最初は、要素が5個前後の小さな配列で十分です。何度か表を書くうちに、found ← false の位置を見ただけで、値ごとに数え直しているのだと分かるようになります。

論理型の変数は値が変わるたびに戻す。迷ったら重複のあとに新しい値が来る例で試す。 この2つを習慣にしておけば、重複を取り除く問題にも自信を持って向き合えます。次に結果の配列を作り直すコードに出会ったら、まずは空の result に最初の値が入るところから表に書いてみてください。