スタックの後入れ先出しから必要な個数を考える
基本情報技術者試験 令和元年度秋期 午前 問8 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
- ア
1
- イ
2
- ウ
3
- エ
4
会話形式の解説
講師まず、SとTを出力するまで取り出せない文字に注目します。ポップすると必ず出力される条件です。
受験者A、C、Kは先に入力されますが、SとTの後まで積んでおく必要がありますね。
講師その通りです。この3文字は入力も出力もA、C、Kの順です。同じスタックに2文字を積むと、取り出す順はどうなりますか。
受験者後から積んだ文字が先に出ます。例えばAの上にCを積むと、Aを先に出せません。
講師そうです。1個ではもちろん、2個でもA、C、Kのうち少なくとも2文字が同じスタックに入ります。その2文字の出力順が逆になるので、どちらも足りません。
受験者では、A、C、Kをそれぞれ別のスタックに積めばよいですか。
講師はい。Sが入力されたら積んですぐ取り出し、Tも同じように出力します。その後、A、C、Kをそれぞれのスタックから順に取り出せます。
受験者3個では実現でき、2個以下では実現できないので、最小は3個ですね。
講師正解はウです。4個でも出力はできますが、最小個数を問われているので選びません。
まとめ
正解はウの3個です。A、C、KはSとTの後に入力順で出力する必要があるため、それぞれ別のスタックに積みます。SとTは入力後すぐに積んで取り出せば、3個で指定順を実現できます。2個以下ではA、C、Kのうち2文字が同じスタックに入り、必要な順に取り出せません。
解答・解説
正解はウです
この問題のテーマ
スタックの後入れ先出しという性質から、指定された出力順に必要なスタックの最小個数を求める問題です。
解き方の考え方
まず、SとTを出力するまで取り出せない文字に注目します。A、C、Kはすべて先に入力されますが、出力はこの3文字も入力と同じ順です。同じスタックに積んだ文字は逆順に取り出されるため、この3文字をどう分けるかが鍵になります。
選択肢ごとの解説
- ×ア 11個では、先に入力されたAの上にCとKが積まれます。S、Tを出力した後にAを取り出そうとしても、上にある文字が先に出るため、指定の順にはできません。
- ×イ 22個では、A、C、Kのうち少なくとも2文字を同じスタックに積む必要があります。その2文字は先に入力された方を先に出力しなければなりませんが、スタックからは後に積んだ方が先に出ます。
- ○ウ 33個を用意し、A、C、Kをそれぞれ別のスタックに積みます。続くSは積んですぐ取り出し、Tも同様にすれば、先にS、Tを出力できます。その後、A、C、Kを順に取り出せるので、3個で実現できます。
- ×エ 44個あれば指定順の出力はできます。ただし、ウの手順で3個あれば足りるため、「最小限必要」とされる個数は4個ではありません。
POINT
- ポップすると必ず出力されるので、後で出力する文字を途中で取り出しておくことはできません。
- 先に入力され、後で入力順に出力する文字同士は、同じスタックに積めるかを確認します。
- 最小個数は、少ない個数では不可能なことと、その個数で実現できることの両方から確かめます。