C++で解く「鳴くカエルの最小数」問題

問題概要

croakOfFrogs という文字列が与えられます。この文字列は、複数のカエルが発する「croak」という鳴き声が混ざり合ってできています。複数のカエルが同時に鳴くこともあるため、複数の「croak」が入り混じった状態になっています。

ここでの課題は、与えられた文字列に含まれるすべての鳴き声を完成させるために必要な「カエルの最小匹数」を求めることです。

有効な「croak」とは、1匹のカエルが 'c'、'r'、'o'、'a'、'k' の5文字を必ずこの順番で発声することを指します。カエルは5文字すべてを出し切って初めて1回の鳴き声が完了します。もし文字列が有効な「croak」の組み合わせとして成立しない場合は -1 を返します。

たとえば入力が "crcoakroak" の場合、出力は 2 になります。1匹目のカエルが先に鳴き始め、その途中で2匹目のカエルが加わることで、合計2匹ですべての鳴き声を完成できるためです。

解法のアプローチ

この問題は、次の手順に従って解きます。

• 各文字の出現回数を記録するマップ m を用意する。
• サイズ5の配列 ch を {'c', 'r', 'o', 'a', 'k'} で初期化する。
• temp = 0（現在鳴いているカエルの数）、ret = 0（答え）とする。
• 文字列 s の各文字 c について以下を繰り返す。
  • m[c] を1増やす。
  • maxVal = m[ch[0]] とする。
  • i を 0〜4 まで動かしながら、maxVal < m[ch[i]] または m[ch[i]] < 0 の場合は -1 を返す。そうでなければ maxVal = m[ch[i]] で更新する。これにより、「前の音より後の音の数が多くなっていないか」、つまり鳴き声の順序が崩れていないかを常に検証できます。
  • c が 'c' なら temp を1増やす（新しいカエルが鳴き始めた）。
  • c が 'k' なら temp を1減らす（1匹分の鳴き声が完了した）。
  • ret = max(ret, temp) として、同時に鳴いていたカエル数の最大値を記録する。
• 最後に i を 1〜4 まで確認し、m[ch[0]] != m[ch[i]] なら -1 を返す。すべての文字の個数が一致していなければ、途中で打ち切られた鳴き声が残っていることを意味します。
• ret を返す。

ポイント解説

変数 temp は「'c' を発声したものの、まだ 'k' で完了していないカエル」、すなわち現在同時に鳴いているカエルの数を表しています。処理中の最大値を ret に記録しておけば、それがまさに必要なカエルの最小匹数となります。さらに、文字ごとの出現回数チェックによって、音の順序が不正な文字列や未完了の鳴き声を含む文字列を -1 として正しく除外できます。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minNumberOfFrogs(string s) {
      map<char, int> m;
      char ch[5] = { 'c', 'r', 'o', 'a', 'k' };
      int temp = 0;
      int ret = 0;
      for (auto& c : s) {
         m[c]++;
         int maxVal = m[ch[0]];
         for (int i = 0; i < 5; i++) {
            if (maxVal < m[ch[i]] || m[ch[i]] < 0) {
               return -1;
            }
            maxVal = m[ch[i]];
         }
         if (c == 'c') {
            temp++;
         }
         else if (c == 'k') {
            temp--;
         }
         ret = max(ret, temp);
      }
      for (int i = 1; i < 5; i++) {
         if (m[ch[0]] != m[ch[i]])
            return -1;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minNumberOfFrogs("crcoakroak"));
}

入力

"crcoakroak"

出力

2