C++のSTLを使って配列が回文かどうかを判定するプログラム

整数 n 個からなる配列 arr[n] が与えられたとき、「その配列は回文（パリンドローム）か？」を判定するのが本稿のテーマです。C++ の STL（標準テンプレートライブラリ）を活用して、この問題をシンプルに解いていきます。

STLとは

STL（Standard Template Library）は、C++ に用意されたテンプレートクラスの集合体で、スタック・キュー・リストといったデータ構造や、ソート・反転などの便利な関数を提供します。これらを活用するには、テンプレートクラスに関する基本的な知識が必要です。本稿では、STL の reverse() 関数を使って配列を反転させています。

回文とは

回文とは、前から読んでも後ろから読んでも同じになる並びのことです。文字列の例としては「MADAM」や「RACECAR」が有名です。配列の場合も同様に、要素を逆順に並べ替えた結果が元の配列と完全に一致すれば、その配列は回文であるといえます。

入力例と出力例

入力：

arr[] = {1, 2, 3, 5, 3, 2, 1}

出力：

回文です

入力：

arr[] = {1, 2, 3, 4, 5}

出力：

回文ではありません

解き方のアプローチ

• フラグ変数 flag を初期値 0 として用意します。
• 元の配列を別の配列 arr_2 にコピーし、STL の reverse() でもう一方を反転させます。
• 両者の要素を先頭から順に比較し、一致しない要素が見つかった時点で flag を 1 に設定してループを抜けます。
• ループ終了後、flag が 0 のままなら「回文です」、1 になっていれば「回文ではありません」を出力します。

なお、コピーを作らずに「先頭と末尾から中央へ向かって arr[i] と arr[n-i-1] を比較していく」双方向ポインタ法を使えば、追加メモリなしで O(n) 時間・O(1) 空間で判定することも可能です。

アルゴリズム

開始
ステップ1 → 配列が回文かどうかを判定する関数を定義する
    void check_palindrome(int arr[], int size)
        int flag = 0 を宣言
        int arr_2[size] を宣言
        memcpy(arr_2, arr, size * sizeof(int)) を呼び出して配列をコピー
        reverse(arr, arr + size) を呼び出して配列を反転
        ループ：int i = 0 から i < size まで i++ ずつ繰り返す
            IF (arr[i] != arr_2[i])
                flag = 1 を設定して Break
            End
        IF (flag == 0)
            「回文です」と出力
        ELSE
            「回文ではありません」と出力
        End
ステップ2 → main() 内での処理
    int arr[] = { 2,3,4,3,2 } を宣言
    int size = sizeof(arr) / sizeof(arr[0]) を宣言
    check_palindrome(arr, size) を呼び出す
終了

サンプルコード

#include <bits/stdc++.h>
using namespace std;

void check_palindrome(int arr[], int size){
    int flag = 0;
    int arr_2[size];
    memcpy(arr_2, arr, size * sizeof(int));
    reverse(arr, arr + size);
    for (int i = 0; i < size; i++)
        if (arr[i] != arr_2[i]){
            flag = 1;
            break;
        }
    if (flag == 0)
        cout << "回文です\n";
    else
        cout << "回文ではありません\n";
}

int main(){
    int arr[] = { 2,3,4,3,2 };
    int size = sizeof(arr) / sizeof(arr[0]);
    check_palindrome(arr, size);
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

回文です

計算量

この手法の時間計算量は O(n) です。また、比較用の補助配列が必要なため、空間計算量は O(n) となります。前述の双方向ポインタ法を採用すれば、補助配列が不要になり、空間計算量を O(1) に抑えることができます。