シアトルからフロリダへのフライト回数が多いか判定するC++プログラム

'S' と 'F' の2種類の文字で構成された文字列 S があるとします。S[i] が 'S' であれば i 日目にはシアトルにいて、'F' であればフロリダにいることを表します。このとき、シアトルからフロリダへ飛行した回数が、フロリダからシアトルへ飛行した回数よりも多いかどうかを判定する必要があります。

例として、入力が S = "SSFFSFFSFF" の場合、出力は True になります。

判定ロジックのポイント

この問題は一見、移動の履歴をすべて数える必要がありそうに思えますが、実は文字列の先頭と末尾の文字だけを見れば判定できます。都市間の移動は必ずフライトを伴うため、旅の開始時にシアトルにおり、終了時にフロリダにいれば、シアトル発のフライトが必ず1回だけ多くなるからです。反対に、開始と終了が同じ都市であれば両方向の回数は同数になり、フロリダで始まってシアトルで終わる場合はフロリダ発のフライトの方が多くなります。

なお、この手法では文字列全体を走査する必要がなく、計算量は O(1) と非常に効率的です。

解決手順

この問題を解くために、以下の手順に従います。

n := 文字列 S の長さ
もし S[0] が 'S' であり、かつ S[n - 1] が 'F' である場合：
    true を返す
そうでない場合：
    false を返す

実装例

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

#include <bits/stdc++.h>
using namespace std;
bool solve(string S)
{
    int n = S.size();
    if (S[0] == 'S' && S[n - 1] == 'F')
        return true;
    else
        return false;
}
int main(){
    string S = "SSFFSFFSFF";
    cout << solve(S) << endl;
}

入力

"SSFFSFFSFF"

出力

1

出力が「1」になるのは、solve 関数が true を返したことを意味します。つまり、この旅程ではシアトルからフロリダへのフライトの方が多いと判定されたことになります。