C++で昇順にソートされていない列の数をカウントする方法

問題概要

同じ長さの文字列からなる配列が与えられたとき、縦方向(列ごと)に見て昇順にソートされていない列がいくつあるかを数えるのが、この問題の目的です。

具体的な手順は次のとおりです。まず、すべての文字列の1文字目同士を上から下へ比較し、続いて2文字目同士、3文字目同士というように、同じ位置にある文字を順番に調べていきます。ある列の中で「前の文字より後ろの文字が小さい」という箇所がひとつでもあれば、その列は昇順ではないと判定し、カウントを1つ増やします。

入力例と出力例

例1:すべての列が昇順の場合

Arr[] = { "abc", "bcd", "def" }

出力:

昇順にソートされていない列の数: 0

解説:各列の文字を確認すると、

• 1列目(インデックス0): a < b < d
• 2列目(インデックス1): b < c < e
• 3列目(インデックス2): c < d < f

すべての列で文字が昇順に並んでいるため、カウントは0となります。

例2:昇順が崩れている列がある場合

Arr[] = { "dbd", "faf", "eeg" }

出力:

昇順にソートされていない列の数: 2

解説:各列の文字を確認すると、

• 1列目(インデックス0): d < f > e … 昇順ではない
• 2列目(インデックス1): b > a < e … 昇順ではない
• 3列目(インデックス2): d < f < g … 昇順

1列目と2列目で昇順が崩れているため、答えは2となります。

アルゴリズムの考え方

• 同じ長さの文字列を2次元の文字配列 arr[][] に格納します。
• 関数 countCols(char str[3][4], int n, int len) は、文字列配列・文字列の本数 n・各文字列の長さ len を引数として受け取り、昇順になっていない列の数を戻り値として返します。
• 変数 count を 0 で初期化します。
• 外側のループで、すべての文字列に共通する文字位置(列のインデックス j)を先頭から末尾まで走査します。
• 内側のループで、各行の j 番目の文字を直下の行と比較し、str[i][j] > str[i+1][j](昇順の崩れ)が検出されたら count を1増やし、その列のチェックを打ち切って次の列へ進みます。
• すべての列を調べ終えたら、count の値を結果として返します。

計算量は O(n × len)(nは文字列の本数、lenは文字列の長さ)であり、非常に効率的です。

C++での実装例

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

// 昇順にソートされていない列の数を数える
int countCols(char str[3][4], int n, int len){
    int count = 0;
    // 共通のインデックス(列)ごとにチェック
    for(int j = 0; j < len; j++){
        for(int i = 0; i < n - 1; i++){
            if(str[i][j] > str[i + 1][j]){
                count++;
                break;
            }
        }
    }
    return count;
}

int main(){
    char arr[3][4] = {"dbd", "faf", "eeg"};
    cout << "昇順にソートされていない列の数:" << countCols(arr, 3, 3) << endl;
    return 0;
}

実行結果

昇順にソートされていない列の数:2

まとめ

本記事では、同じ長さの文字列配列を縦方向(列単位)に走査し、昇順に並んでいない列の数を数えるC++プログラムを紹介しました。ポイントは、行方向ではなく列方向に隣接する文字を比較すること、そして昇順の崩れを一度でも検出した時点でその列をカウントし、次の列へ進むことです。文字列処理と2次元配列操作の基礎を固めるのに最適な練習問題なので、ぜひ自分のコードでも試してみてください。