C++で文字列をソート順に並べ替え、数字の合計を末尾に追加する方法

問題の概要

本記事では、アルファベットと数字が混在する文字列を扱う問題を解説します。具体的には、アルファベット部分を辞書順に並べ替え、さらに文字列内のすべての数字を合計した値を末尾に追加するという処理を行います。

入力 : str = "adv4fc3"
出力 : "acdfv7"
説明: すべての文字が「acdfv」にソートされ、その後に整数4と3の合計「7」が続きます。

入力 : str = "h2d7e3f"
出力 : "defh12"
説明: すべての文字が「defh」にソートされ、その後に整数2、7、3の合計「12」が続きます。

解決のためのアプローチ

この問題では、2つのタスクを実行する必要があります。1つは文字列のソート、もう1つは整数値の合計計算です。

• 文字列のソートは、各文字の出現回数をカウントしておき、そのカウントに基づいて新しい文字列へ文字を挿入していくことで実現できます。

• 整数の合計は、数字が出現するたびに変数へ加算していくことで求められます。

サンプルコード

上記アプローチのC++コード

#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
int main(){
    string str = "h2d7e3f";
    int ch[26] = {0};
    int count = 0;
    // 文字列のすべての文字を走査する
    for (int i = 0; i < str.length(); i++){
        // 各文字の出現回数をカウントする
        if (str[i]>='a' && str[i] <='z')
            ch[str[i] - 97] = ch[str[i] - 97] + 1;
        // 数字が出現した場合
        else
            count = count + (str[i]-'0');
    }
    string final = "";
    // ch配列を使ってソート済みの文字列を構築する
    for (int i = 0; i < 26; i++){
        char a = (char)('a'+i);
        // 現在の文字をカウントが尽きるまで新しい文字列に挿入する
        while (ch[i]-- != 0)
            final = final + a;
    }
    // 最後に、集計した数字の合計を文字列に追加する
    if (count>0)
        final = final + to_string(count);
    cout << "Rearranged string: " << final;
    return 0;
}

出力結果

Rearranged string: defh12

コードの解説

• 配列chはサイズ26で初期化されています。これは、アルファベット26文字それぞれの出現回数を記録する必要があるためです。

• 最初のループでは文字列を先頭から走査します。アルファベットの場合は該当する文字のカウントを1つ増やし、数字の場合はcount変数にその値を加算します。

• 2番目のループでは、カウント配列をもとにソート済みの新しい文字列を構築します。各文字を出現回数の分だけ順番に文字列へ追加していきます。

• 最後に、最初のループで集計した数字の合計を、文字列の末尾に追加して完成させます。

まとめ

本チュートリアルでは、文字列をソート順に並べ替え、数字の合計を末尾に追加する方法について、カウント配列(ハッシュテーブルの考え方)を使った効率的なアプローチで解説しました。C++での実装コードを紹介しましたが、同じロジックはC、Java、Pythonなど他のプログラミング言語でも容易に実装できます。本チュートリアルが皆さんの学習に役立てば幸いです。