E/Nシーケンスから配列を再構成できるか判定するC++コード

問題概要

長さnの文字列Sが与えられます。ここで、n個の数値が円状(環状)に並んでいると考えます。数値の実際の値は不明ですが、S[i] = 'E'であればi番目と(i+1)番目の数値が等しく、'N'であれば異なることを示しています。文字列Sの情報をもとに、この数列を実際に再構成できるかどうかを判定します。

例えば、入力がS = "ENNEENE"の場合、[15, 15, 4, 20, 20, 20, 15]という値を割り当てることができるため、出力はTrueになります。

解法のポイント

この問題の鍵は、数列が円状に並んでいる点にあります。文字列中に'N'がちょうど1つだけ含まれるケースを考えてみましょう。この場合、残りのすべての隣接ペアは'E'、すなわち「等しい」ことを要求します。環状構造では'E'でつながった要素はすべて同一の値を持たなければならないため、唯一の'N'が示す「異なる」という条件と矛盾が生じてしまいます。

したがって、判定ロジックは以下のようになります。

• 文字列Sに'N'がちょうど1つだけ含まれる場合 → false(再構成不可能)
• それ以外('N'が0個、または2個以上)の場合 → true(再構成可能)

アルゴリズムの手順

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

if Sに'N'が1つだけ含まれている場合:
    return false
return true

実装例

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

#include<bits/stdc++.h>
using namespace std;
bool solve(string S){
    if (count(S.begin(), S.end(), 'N') == 1)
        return false;
    return true;
}
int main(){
    string S = "ENNEENE";
    cout << solve(S) << endl;
}

入力

"ENNEENE"

出力

1

計算量の分析

時間計算量はO(n)(文字列を一度走査して'N'をカウントするため)、空間計算量はO(1)となります。非常にシンプルかつ効率的なアルゴリズムです。