令和元年度 秋期 基本情報技術者試験 問8

解説

正解はウ。 出力順S,T,A,C,Kを実現するには，各文字を入力順の逆順(降順)で取り出せるスタックに割り当てる必要がある。 出力順を入力位置番号で表すと4,5,1,2,3となり，この列を最小個数の広義単調減少列に分割すると{4,5}と{1,2,3}の2組では足りず3組必要になる(最長増加部分列4,5や1,2,3の長さが3)ため，最小のスタック数は3である。