FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
文字列 s="(())()" に対して、次の手続 maxDepth(s) を実行したときの戻り値はどれか。
○整数型: maxDepth(文字列型: s)
整数型: i, depth ← 0, max ← 0
for (i を 1 から sの文字数 まで 1 ずつ増やす)
if (sのi文字目 = "(")
depth ← depth ＋ 1
if (depth ＞ max)
max ← depth
endif
else
depth ← depth - 1
endif
endfor
return max- ア 1
- イ 2
- ウ 3
- エ 0
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：2
正解：2
括弧の深さは、開き括弧で1増え、閉じ括弧で1減るスタックの積み上がりとして考える。ここでは実際に配列スタックを使っていないが、depth がスタックに積まれている開き括弧の数を表す。
(())()では、2文字目を読んだ時点で depth が2になり、これが最大である。その後は閉じ括弧で0に戻り、最後の()では深さ1までしか増えない。
| 文字 | depth | max |
|---|---|---|
| ( | 1 | 1 |
| ( | 2 | 2 |
| ) | 1 | 2 |
| ) | 0 | 2 |
| ( | 1 | 2 |
| ) | 0 | 2 |
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。